2689. Extract Kth Character From The Rope Tree

Approach 1: Recursive

• Time: $O(n)$
• Space: $O(\log n)$

C++JavaPython

class Solution {
 public:
  char getKthCharacter(RopeTreeNode* root, int k) {
    if (root->len == 0)
      return root->val[k - 1];
    const int leftLen =
        root->left == nullptr
            ? 0
            : max(root->left->len, static_cast<int>(root->left->val.length()));
    return leftLen >= k ? getKthCharacter(root->left, k)
                        : getKthCharacter(root->right, k - leftLen);
  }
};

class Solution {
  public char getKthCharacter(RopeTreeNode root, int k) {
    if (root.len == 0)
      return root.val.charAt(k - 1);
    final int leftLen = root.left == null ? 0 : Math.max(root.left.len, root.left.val.length());
    return leftLen >= k ? getKthCharacter(root.left, k) : getKthCharacter(root.right, k - leftLen);
  }
}

class Solution:
  def getKthCharacter(self, root: Optional[object], k: int) -> str:
    """:type root: Optional[RopeTreeNode]"""
    if root.len == 0:
      return root.val[k - 1]
    leftLen = 0 if root.left is None \
        else max(root.left.len, len(root.left.val))
    if leftLen >= k:
      return self.getKthCharacter(root.left, k)
    return self.getKthCharacter(root.right, k - leftLen)

Approach 2: Iterative

• Time: $O(n)$
• Space: $O(\log n)$

C++Java

class Solution {
 public:
  char getKthCharacter(RopeTreeNode* root, int k) {
    while (root->len > 0) {
      const int leftLen = root->left == nullptr
                              ? 0
                              : max(root->left->len,
                                    static_cast<int>(root->left->val.length()));
      if (leftLen >= k) {
        root = root->left;
      } else {
        root = root->right;
        k -= leftLen;
      }
    }
    return root->val[k - 1];
  }
};

class Solution {
  public char getKthCharacter(RopeTreeNode root, int k) {
    while (root.len > 0) {
      final int leftLen = root.left == null ? 0 : Math.max(root.left.len, root.left.val.length());
      if (leftLen >= k) {
        root = root.left;
      } else {
        root = root.right;
        k -= leftLen;
      }
    }
    return root.val.charAt(k - 1);
  }
}