2689. Extract Kth Character From The Rope Tree

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".

/**
 * 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 {
    char dfs(RopeTreeNode* n, int k) {
        if(n->len == 0) return n->val[k-1];
        if(!n->left) return dfs(n->right,k);
        if(!n->right) return dfs(n->left,k);
        if(n->left->len >= k) return dfs(n->left,k);
        if(n->left->len == 0 and n->left->val.length() >= k) return dfs(n->left,k);
        return dfs(n->right, k - max(n->left->len, (int)n->left->val.length()));
    }
public:
    char getKthCharacter(RopeTreeNode* root, int k) {
        return dfs(root,k);
    }
};