LeetCode Problem 2689

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Edit

LeetCode 2689 - Extract Kth Character From The Rope Tree

Problem Understanding

This problem asks us to retrieve the k-th character from a string represented by a special binary tree called a rope tree. Instead of storing one large string directly, the string is distributed across the tree structure.

Each node in the tree belongs to one of two categories.

A leaf node stores an actual string inside node.val. Since leaf nodes represent real pieces of text, they always contain a non-empty string and have node.len = 0.

An internal node does not store text directly. Instead, it represents the concatenation of its left and right subtrees. These nodes always have an empty string as node.val and a positive integer node.len, which stores the total length of the concatenated string represented by that subtree.

The complete string represented by the tree is defined recursively:

• For a leaf node, the represented string is simply node.val.
• For an internal node, the represented string is formed by concatenating the string from the left subtree with the string from the right subtree.

The goal is to return the k-th character of the full string represented by the root node.

An important detail is that k is 1-indexed, meaning:

• k = 1 refers to the first character
• k = 2 refers to the second character
• and so on

For example, if the represented string is "grtaabcpoe" and k = 6, we return the sixth character, which is "b".

The constraints tell us several useful things about the input size and behavior. The number of nodes is at most 1000, and each leaf string has a maximum length of 50. While this is not very large, the total rope length can still reach 10^4. More importantly, the problem structure suggests that building the entire string may be unnecessary. Since we only need one character, reconstructing everything would perform more work than needed.

The problem also guarantees several helpful properties:

• Every leaf node contains a non-empty string.
• Every internal node has a valid positive len.
• k is always valid, meaning it will always fall within the total string length.
• The tree is guaranteed to represent a valid rope.

These guarantees mean we do not need to handle invalid input or out-of-bounds access.

There are several edge cases worth identifying upfront. The root itself may be a single leaf node, meaning the answer comes directly from one string without traversal. The desired character may lie exactly at the boundary between the left and right subtree. Some internal nodes may only have one child, so the traversal logic must safely handle missing children. Finally, deeply nested trees could cause inefficient repeated string concatenation in a naive solution.

Approaches

Brute Force Approach

The most straightforward idea is to reconstruct the full string represented by the rope tree and then directly access the k-th character.

We can perform a depth-first traversal:

• If the current node is a leaf, return its string.
• If the node is internal, recursively construct the left string and right string, then concatenate them.

After generating the entire string for S[root], we simply return:

S[root][k - 1]

because Python and Go use zero-based indexing.

This approach is correct because it faithfully follows the recursive definition of the rope tree. Every internal node concatenates its children in the proper order, so the final constructed string exactly matches S[root].

However, this solution is wasteful. We only need one character, yet we reconstruct the entire string. Since repeated string concatenation can be expensive, especially for deeply nested trees, we do unnecessary work.

Optimal Approach

The key observation is that we do not need to construct the full string.

Each internal node already tells us the total length of the string represented by its subtree through node.len. This allows us to determine whether the target character belongs in the left subtree or the right subtree.

At any internal node:

1. Compute the length of the left subtree.
2. If k is less than or equal to that length, the desired character must be inside the left subtree.
3. Otherwise, the character belongs to the right subtree, and we adjust k by subtracting the left subtree length.

Eventually, we reach a leaf node, where the answer becomes a simple character lookup inside node.val.

This works because rope trees are fundamentally built around splitting strings into segments while storing length metadata. Instead of rebuilding the entire string, we navigate directly to the correct leaf.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N + L)	O(L)	Reconstructs the entire string before indexing
Optimal	O(H)	O(H)	Traverses only one path to the target character

Here:

• N is the number of nodes.
• L is the total string length.
• H is the tree height.

Algorithm Walkthrough

1. Start traversal at the root node.

We repeatedly decide whether the desired character lies in the left subtree or right subtree. Since the rope stores subtree lengths, we can make this decision without building strings. 2. Check whether the current node is a leaf.

A leaf node contains the actual text in node.val. Since leaf nodes represent concrete string segments, we can directly return:

node.val[k - 1]

because k is one-indexed. 3. Determine the left subtree length.

If a left child exists, compute its represented length.

If the left child is a leaf, its length is:

len(node.left.val)

Otherwise, for an internal node:

node.left.len

4. Decide which subtree contains the answer.

If:

k <= left_length

then the target character lies inside the left subtree, so move left.

Otherwise, move right and subtract the skipped characters:

k -= left_length

5. Repeat until reaching a leaf.

Since every step eliminates one subtree from consideration, the search continuously narrows toward the exact location of the desired character.

Why it works

The correctness comes from maintaining a simple invariant:

At every step, k always represents the position of the target character within the current subtree.

Initially, k refers to the target position inside S[root]. When moving left, the position remains unchanged because the character still lies in the left subtree. When moving right, we subtract the left subtree size because those characters come before the right subtree in concatenation order. Eventually, we reach a leaf where the invariant guarantees that k directly indexes the correct character.

Python Solution

# Definition for a rope tree node.
# class RopeTreeNode(object):
#     def __init__(self, len=0, val="", left=None, right=None):
#         self.len = len
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def getKthCharacter(self, root: Optional[object], k: int) -> str:
        current = root

        while current:
            # Leaf node
            if current.left is None and current.right is None:
                return current.val[k - 1]

            left_length = 0

            if current.left:
                if current.left.len == 0:
                    left_length = len(current.left.val)
                else:
                    left_length = current.left.len

            if k <= left_length:
                current = current.left
            else:
                k -= left_length
                current = current.right

        return ""

The implementation uses an iterative traversal instead of recursion. This avoids recursive call overhead and keeps memory usage minimal.

We begin at the root and repeatedly move toward the correct subtree. If the current node is a leaf, we immediately return the character at position k - 1.

For internal nodes, we calculate the effective size of the left subtree. This step is important because leaf nodes have len = 0, so we cannot rely on node.len for leaves. Instead, we use the actual string length for leaf nodes.

After computing the left subtree size, we determine whether the target character belongs to the left or right side. If it lies on the right, we subtract the left subtree size to maintain the correct relative index.

The loop continues until a leaf node is reached.

Go Solution

/**
 * Definition for a rope tree node.
 * type RopeTreeNode struct {
 *     len   int
 *     val   string
 *     left  *RopeTreeNode
 *     right *RopeTreeNode
 * }
 */

func getKthCharacter(root *RopeTreeNode, k int) byte {
	current := root

	for current != nil {
		// Leaf node
		if current.left == nil && current.right == nil {
			return current.val[k-1]
		}

		leftLength := 0

		if current.left != nil {
			if current.left.len == 0 {
				leftLength = len(current.left.val)
			} else {
				leftLength = current.left.len
			}
		}

		if k <= leftLength {
			current = current.left
		} else {
			k -= leftLength
			current = current.right
		}
	}

	return 0
}

The Go solution follows the same logic as the Python version but adapts to Go syntax and type handling.

In Go, strings are byte indexed, so accessing:

current.val[k-1]

returns a byte, which matches the required return type.

We also explicitly check for nil pointers before accessing child nodes. Since the problem guarantees valid input, the fallback return value of 0 should never actually execute.

Worked Examples

Example 1

Input

root = [10,4,"abcpoe","g","rta"]
k = 6

Represented string:

"grtaabcpoe"

Current Node	Left Length	k	Decision
Root (10)	4	6	Move right, k = 6 - 4 = 2
"abcpoe"	-	2	Return 'b'

Final answer:

"b"

Example 2

Input

root = [12,6,6,"abc","efg","hij","klm"]
k = 3

Represented string:

"abcefghijklm"

Current Node	Left Length	k	Decision
Root (12)	6	3	Move left
Internal (6)	3	3	Move left
"abc"	-	3	Return 'c'

Final answer:

"c"

Example 3

Input

root = ["ropetree"]
k = 8

Since the root is already a leaf node:

"ropetree"[7] = 'e'

Final answer:

"e"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(H)	We only traverse one root-to-leaf path
Space	O(1) iterative, O(H) recursive	The iterative version uses constant extra memory

The algorithm never visits the entire tree unless necessary. At each internal node, we choose exactly one subtree and discard the other. This means the traversal follows only a single path from root to leaf, giving a runtime proportional to the tree height H.

Because the implementation is iterative, it uses constant extra memory. A recursive implementation would instead consume stack space proportional to the height of the tree.

Test Cases

# Helper class for testing
class RopeTreeNode:
    def __init__(self, len=0, val="", left=None, right=None):
        self.len = len
        self.val = val
        self.left = left
        self.right = right

solution = Solution()

# Example 1
root1 = RopeTreeNode(
    10,
    "",
    RopeTreeNode(4, "", RopeTreeNode(0, "g"), RopeTreeNode(0, "rta")),
    RopeTreeNode(0, "abcpoe")
)
assert solution.getKthCharacter(root1, 6) == "b"  # provided example

# Example 2
root2 = RopeTreeNode(
    12,
    "",
    RopeTreeNode(6, "", RopeTreeNode(0, "abc"), RopeTreeNode(0, "efg")),
    RopeTreeNode(6, "", RopeTreeNode(0, "hij"), RopeTreeNode(0, "klm"))
)
assert solution.getKthCharacter(root2, 3) == "c"  # provided example

# Example 3
root3 = RopeTreeNode(0, "ropetree")
assert solution.getKthCharacter(root3, 8) == "e"  # single leaf root

# Single character leaf
root4 = RopeTreeNode(0, "x")
assert solution.getKthCharacter(root4, 1) == "x"  # smallest valid input

# Boundary between left and right subtree
root5 = RopeTreeNode(
    6,
    "",
    RopeTreeNode(0, "abc"),
    RopeTreeNode(0, "def")
)
assert solution.getKthCharacter(root5, 3) == "c"  # last char of left
assert solution.getKthCharacter(root5, 4) == "d"  # first char of right

# Deeply nested tree
root6 = RopeTreeNode(
    7,
    "",
    RopeTreeNode(
        4,
        "",
        RopeTreeNode(0, "ab"),
        RopeTreeNode(0, "cd")
    ),
    RopeTreeNode(0, "xyz")
)
assert solution.getKthCharacter(root6, 5) == "x"  # traversal into right subtree

# k equals total length
assert solution.getKthCharacter(root6, 7) == "z"  # last character

Test	Why
Example 1	Verifies traversal into right subtree
Example 2	Verifies multiple internal nodes
Example 3	Tests single leaf root
Single character leaf	Tests smallest valid input
Boundary positions	Verifies exact left/right split handling
Deeply nested tree	Ensures traversal works through multiple levels
k = total length	Tests final character access

Edge Cases

One important edge case occurs when the root itself is a leaf node. In this scenario, there are no children to traverse, and the answer must be returned directly from the root string. A naive traversal may assume every node has children and fail with null access. Our implementation explicitly checks for leaf nodes first, making this case work naturally.

Another tricky case happens when **k**** lies exactly at the boundary between the left and right subtree**. For example, if the left subtree contributes three characters, then k = 3 belongs to the left subtree, while k = 4 belongs to the right subtree. Off-by-one mistakes are very common here. Our implementation correctly uses:

k <= left_length

to ensure boundary positions are handled properly.

A third important edge case involves **leaf nodes having ****len = 0**. Since internal nodes store their subtree size in len, one might incorrectly assume every node behaves the same way. However, leaf nodes intentionally use len = 0, even though they contain characters. We solve this by checking whether a node is a leaf and using:

len(node.val)

instead of node.len when necessary.

Finally, some rope trees may be highly unbalanced, resembling linked lists more than balanced binary trees. A brute-force string construction solution may repeatedly concatenate strings inefficiently. Our approach remains efficient because it only follows one root-to-leaf path and ignores irrelevant subtrees.