We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Extract Kth Character From The Rope Tree

Number: 2843

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Given the root of a rope binary tree where leaf nodes store non‐empty strings and internal nodes are used to “glue” the leaves together with a precomputed total length in a node.len field, return the kth character of the resulting string S[root]. Note that S[node] is formed via a recursive concatentation of its children (or its own value if it is a leaf).

Key Insights

  • The rope tree structure lets you locate a particular character without fully constructing the concatenated string.
  • For leaf nodes (with no children), simply return the kth character from the node’s string.
  • For internal nodes, determine whether k falls in the left subtree or the right subtree by using the length of the left subtree.
  • Use recursion: if k is less than or equal to the left subtree’s length, search left; otherwise search right with k adjusted by subtracting the left length.
  • Use a helper to correctly obtain the effective length at a node (since leaves have node.len = 0 but the string length is len(node.val)).

Space and Time Complexity

Time Complexity: O(h) in the average case, where h is the height of the tree. In the worst-case (a skewed tree), it is O(n) with n being the number of nodes. Space Complexity: O(h) due to the recursive call stack.

Solution

The solution uses a recursive depth-first search (DFS) to traverse the rope tree. At each internal node, the effective length of the left subtree is determined using the precomputed length (for internal nodes) or the actual string length (for leaves). Depending on the value of k relative to the left subtree's length, we either recursively search in the left or in the right subtree (after adjusting k by subtracting the left-subtree length). For leaf nodes, the kth character is directly returned from the stored string. This approach avoids concatenating the entire string and efficiently finds the desired character.

Code Solutions

# Definition for a RopeNode.
# class RopeNode:
#     def __init__(self, val="", length=0, left=None, right=None):
#         self.val = val       # The string at the node (non-empty if leaf)
#         self.len = length    # For internal nodes, the total length of S[node]. For leaves, it is 0.
#         self.left = left     # Left child
#         self.right = right   # Right child

def extractKthChar(root, k):

    # Helper to determine the effective length of a node.
    def getLength(node):
        # If the node is a leaf, its effective length is the length of its string.
        if not node.left and not node.right:
            return len(node.val)
        # Otherwise, the length is precomputed in node.len.
        return node.len

    # Recursive DFS function to find the kth character.
    def dfs(node, k):
        # Base case: if the node is a leaf, simply return the kth character (1-indexed).
        if not node.left and not node.right:
            return node.val[k - 1]
        
        # Determine the length of the left subtree.
        left_length = getLength(node.left) if node.left else 0

        # If k is within the left subtree, search there.
        if k <= left_length:
            return dfs(node.left, k)
        # Otherwise, search in the right subtree adjusting k.
        else:
            return dfs(node.right, k - left_length)
    
    return dfs(root, k)
← Back to All Questions