# 2689. Extract Kth Character From The Rope Tree

## Approach 1: Recursive

• Time: $O(n)$
• Space: $O(\log n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 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(root->left->val.length())); return leftLen >= k ? getKthCharacter(root->left, k) : getKthCharacter(root->right, k - leftLen); } }; 
 1 2 3 4 5 6 7 8 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); } } 
  1 2 3 4 5 6 7 8 9 10 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)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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(root->left->val.length())); if (leftLen >= k) { root = root->left; } else { root = root->right; k -= leftLen; } } return root->val[k - 1]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 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); } }