[Google Question] Given a binary tree with string stored leaf node and number of characters in left subtree stored in other nodes, get the substring given index and length.

Problem: You are given a binary tree in which every leaf node has a string and other nodes have the number of characters in their left subtree.  

Given an index and length, return the substring from the binary tree. 

Example:

Input: Tree: above tree, index = 2, length = 10
Output: As pointed in the image "cdefghijkl"
Explanation: If you see the string is "abcdefghilmno", Its substring (2, 10) is "cdefghijkl".

Approach: We can use preorder traversal here. We need to first find the character at given index. Once we find that character, after that we don't need index (we can make it 0) as we just need "length" number of characters.  

Look at the implementation to understand the approach in detail.

Implementation in C#:

      public static string GetString(BinaryTreeStringNode root, int index, int len) 

        { 

            if (root == null) 

            { 

                return string.Empty; 

            } 

            return GetStringInternal(root, ref index, len); 

        } 

        private static string GetStringInternal(BinaryTreeStringNode node, ref int index, int len) 

        { 

            if (node == null) 

            { 

                return string.Empty; 

            } 

            // Got the leaf node, get the substring 

            if (node.Left == null && node.Right == null) 

            { 

                string result = node.Value.Substring(index, len); 

                // Get the starting point, now make index 0 as we just need 'len' number of chars 

                index = 0; 

                return result; 

            } 

            int leftCharsLength = int.Parse(node.Value); 

            // No need to go to left subtree 

            if (leftCharsLength <= index) 

            { 

                index = index - leftCharsLength; 

                return GetStringInternal(node.Right, ref index, len); 

            } 

            // No need to go to right subtree 

            if (leftCharsLength >= index + len) 

            { 

                return GetStringInternal(node.Left, ref index, len); 

            } 

            int numCharsFoundInLeftTree = leftCharsLength - index; 

            return GetStringInternal(node.Left, ref index, numCharsFoundInLeftTree) + GetStringInternal(node.Right, ref index, len - numCharsFoundInLeftTree); 

        }

Complexity: O(n) assuming string operation will take constant time.