LeetCode 2689: Extract Kth Character From The Rope Tree

Explanation

To solve this problem, we can represent the rope as a binary tree where each node stores a string. We can traverse the tree in an inorder manner to concatenate all the strings and then extract the kth character from the concatenated string.

Here are the steps:

1. Build the rope tree by constructing a binary tree where each leaf node contains a single character string and each non-leaf node contains the concatenation of its children's strings.
2. Perform an inorder traversal of the rope tree to concatenate all the strings.
3. Return the kth character from the concatenated string.

Time complexity: O(n) where n is the total number of characters in the rope tree. Space complexity: O(n) for building the rope tree.

class TreeNode {
    String val;
    TreeNode left, right;
    public TreeNode(String val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class RopeTree {
    public String extractKthCharacter(TreeNode root, int k) {
        StringBuilder sb = new StringBuilder();
        inorderTraversal(root, sb);
        return String.valueOf(sb.charAt(k - 1));
    }

    private void inorderTraversal(TreeNode node, StringBuilder sb) {
        if (node == null) return;
        inorderTraversal(node.left, sb);
        sb.append(node.val);
        inorderTraversal(node.right, sb);
    }
}