extract-kth-character-from-the-rope-tree.cpp

// Time:  O(h)
// Space: O(1)

// binary search tree
class Solution {
public:
    char getKthCharacter(RopeTreeNode* root, int k) {
        while (root->len) {
            const int l = root->left ? max(root->left->len, static_cast<int>(size(root->left->val))) : 0;
            if (k <= l) {
                root = root->left;
            } else {
                k -= l;
                root = root->right;
            }
        }
        return root->val[k - 1];
    }
};