Extract Kth Character From The Rope Tree - Practice Coding Problems

Extract Kth Character From The Rope Tree - Problem

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

Input & Output

Example 1 — Basic Rope Tree

$ Input: root = [10,4,"world","hell","o "], k = 6

› Output: " "

💡 Note: The rope represents "hello world". The 6th character (1-indexed) is the space character between "hello" and "world".

Example 2 — Simple Leaf

$ Input: root = ["abc"], k = 2

› Output: "b"

💡 Note: Single leaf node with "abc". The 2nd character is 'b'.

Example 3 — Larger Tree

$ Input: root = [12,6,"hello","prog","ram"], k = 8

› Output: "e"

💡 Note: The rope represents "program" + "hello" = "programhello". The 8th character is 'e' from "hello".

Constraints

The sum of node.val.length over all leaf nodes ≤ 10⁴
1 ≤ k ≤ S[root].length
node.val contains only lowercase English letters
The tree has at most 1000 nodes

Visualization

Tap to expand

Understanding the Visualization

Rope Tree Structure

Internal nodes store length, leaves store actual text

String Representation

Tree represents concatenated string 'hello world'

Character Extraction

Navigate to find k-th character efficiently

Key Takeaway

🎯 Key Insight: Use node length information to navigate directly to the target character without building the entire string

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use the length information in internal nodes to navigate efficiently without constructing the entire string. The optimal approach uses DFS with length-based navigation to find the k-th character in O(h) time where h is tree height. Time: O(h), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS Navigation	O(h)	O(h)	Navigate directly to the k-th character using node length information
Build Complete String	O(n)	O(n)	Construct the entire rope string then return the k-th character

Optimized DFS Navigation — Algorithm Steps

Step 1: At each internal node, check left subtree size using node.len
Step 2: If k <= left_size, search in left subtree
Step 3: Otherwise, search in right subtree with adjusted k
Step 4: Return character directly when reaching leaf node

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare k with left subtree size

k=6, left_length=4, so go right

Adjust k for right subtree

Search for (k-4)=2nd char in right subtree

Found target

Return 'o' (2nd char of 'world')

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    char* val;
    int len;
    struct TreeNode* left;
    struct TreeNode* right;
};

int getLength(struct TreeNode* node) {
    if (!node) return 0;
    if (!node->left && !node->right) return strlen(node->val);
    return node->len;
}

char findKthChar(struct TreeNode* node, int k) {
    if (!node) return ' ';
    
    // Leaf node
    if (!node->left && !node->right) {
        return node->val[k - 1];
    }
    
    // Internal node
    int leftLength = node->left ? getLength(node->left) : 0;
    
    if (k <= leftLength) {
        return findKthChar(node->left, k);
    } else {
        return findKthChar(node->right, k - leftLength);
    }
}

char solution(struct TreeNode* root, int k) {
    return findKthChar(root, k);
}

int main() {
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = "";
    root->len = 10;
    
    struct TreeNode* left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    left->val = "";
    left->len = 4;
    
    struct TreeNode* right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    right->val = "world";
    right->len = 0;
    
    struct TreeNode* leftLeft = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    leftLeft->val = "hell";
    leftLeft->len = 0;
    leftLeft->left = leftLeft->right = NULL;
    
    struct TreeNode* leftRight = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    leftRight->val = "o ";
    leftRight->len = 0;
    leftRight->left = leftRight->right = NULL;
    
    left->left = leftLeft;
    left->right = leftRight;
    right->left = right->right = NULL;
    root->left = left;
    root->right = right;
    
    int k;
    scanf("%d", &k);
    
    char result = solution(root, k);
    printf("%c\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(h)

Only traverse the path from root to the target leaf, where h is tree height

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height for the path traversal

✓ Linear Space

12.5K Views

Medium Frequency

~15 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS Navigation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler