Extract kth character from the rope tree

Tree Depth-First Search Binary Tree

73.3% acceptance

Mar 31, 2026

You are given the root of a binary tree and an integer k. Besides the left and right children, every node of this tree has two other properties, a string node.val containing only lowercase English letters (possibly empty) and a non-negative integer node.len. There are two types of nodes in this tree: Leaf: These nodes have no children, node.len = 0, and node.val is some non-empty string. Internal: These nodes have at least one child (also at most two children), node.len > 0, and node.val is an empty string. The tree described above is called a Rope binary tree. Now we define S[node] recursively as follows: If node is some leaf node, S[node] = node.val, Otherwise if node is some internal node, S[node] = concat(S[node.left], S[node.right]) and S[node].length = node.len. Return k-th character of the string S[root]. Note: If s and p are two strings, concat(s, p) is a string obtained by concatenating p to s. For example, concat("ab", "zz") = "abzz".

Solution

C++

Time O(1)

Space O(1)

LeetCode

solution.cpp

/**
 * Definition for a rope tree node.
 * struct RopeTreeNode {
 *     int len;
 *     string val;
 *     RopeTreeNode *left;
 *     RopeTreeNode *right;
 *     RopeTreeNode() : len(0), val(""), left(nullptr), right(nullptr) {}
 *     RopeTreeNode(string s) : len(0), val(std::move(s)), left(nullptr), right(nullptr) {}
 *     RopeTreeNode(int x) : len(x), val(""), left(nullptr), right(nullptr) {}
 *     RopeTreeNode(int x, RopeTreeNode *left, RopeTreeNode *right) : len(x), val(""), left(left), right(right) {}
 * };
 */
class Solution {
public:
  char getKthCharacter(RopeTreeNode* root, int k) {
    if (!root) return '\0';
    // Leaf node
    if (root->len == 0) {
      return root->val[k - 1];
    }
    // Internal node: S[node] = concat(S[left], S[right]), length = node->len
    int leftLen = getLength(root->left);
    if (k <= leftLen) {
      return getKthCharacter(root->left, k);
    } else {
      return getKthCharacter(root->right, k - leftLen);
    }
  }
  
  int getLength(RopeTreeNode* root) {
    if (!root) return 0;
    if (root->len == 0) return root->val.size();
    return root->len;
  }
};