[Facebook Question][LeetCode] Construct Binary Tree from String

Problem: You need to construct a binary tree from a string consisting of parenthesis and integers.

The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure.

You always start to construct the left child node of the parent first if it exists.

Example:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

Input: s = "4(2(3)(1))(6(5)(7))"
Output: [4,2,6,3,1,5,7]

Input: s = "-4(2(3)(1))(6(5)(7))"
Output: [-4,2,6,3,1,5,7]

Approach: Just by looking at the examples, we can tell the input strings are kind of preorder traversal result so we are going to use preorder traversal only. 

The only thing which we need to do is we need to get the left tree ending index in advance. Here is how our algorithm will look like:

• StrToTree(s, start, end)
• IF (start > end)
• RETURN null
• leftparanthesisStartIndex = Index of '(' in s[start...end]
• IF no '(' in s[start...end]
• RETURN new BinaryTreeNode(int(s[start...end]) // no subtrees just return the node
• node = new BinaryTreeNode(int(s[start...leftparanthesisStartIndex - 1])
• leftparanthesisEndIndex = Index of ')' corresponding to '(' at leftparanthesisStartIndex in s[leftparanthesisStartIndex...end]
• // Recursive calls
• node.Left = CALL StrToTree(s, leftparanthesisStartIndex + 1, leftparanthesisEndIndex - 1) // No need to include '(' and ')'
• node.Right = CALL StrToTree( leftparanthesisEndIndex + 2, end - 1) // +2 is to skip ')' and '('
• RETURN node 

That's all!

Implementation in C#:

    public BinaryTreeNode Str2tree(string s) 

    {

        return this.Str2tree(s, 0, s.Length - 1);

    }

    

    private BinaryTreeNode Str2tree(string s, int startIndex, int endIndex)

    {

        if (startIndex > endIndex)

        {

            return null;

        }

        int leftTreeStartIndex = this.GetLeftTreeStartIndex(s, startIndex, endIndex);

        if (leftTreeStartIndex == -1)

        {

            return new BinaryTreeNode(int.Parse(s.Substring(startIndex, endIndex - startIndex + 1)));

        }

        BinaryTreeNode node = new BinaryTreeNode(int.Parse(s.Substring(startIndex, leftTreeStartIndex - startIndex)));

        int leftTreeEndIndex = this.GetLeftTreeEndIndex(s, leftTreeStartIndex, endIndex);

        // leftTreeEndIndex == -1: Should not happen

        if (leftTreeEndIndex != -1)

        {

            node.LeftNode = this.Str2tree(s, leftTreeStartIndex + 1, leftTreeEndIndex - 1);

            node.RightNode = this.Str2tree(s, leftTreeEndIndex + 2, endIndex - 1);

        }

        return node;

    }

    

    private int GetLeftTreeEndIndex(string s, int leftTreeStartIndex, int endIndex)

    {

        int leftPranthesisCount = 0;

        for (int i = leftTreeStartIndex; i <= endIndex; ++i)

        {

            if (s[i] == '(')

            {

                ++leftPranthesisCount;

            }

            else if (s[i] == ')')

            {

                --leftPranthesisCount;

            }

            // Get the corresponding ')'

            if (leftPranthesisCount == 0)

            {

                return i;

            }

        }

        return -1;

    }

    

    private int GetLeftTreeStartIndex(string s, int startIndex, int endIndex)

    {

        for (int i = startIndex; i < endIndex; ++i)

        {

            if (s[i] == '(')

            {

                return i;

            }

        }

        return -1;

    }

Complexity: O(n)