Problem statement

https://leetcode.com/problems/construct-binary-tree-from-string/

Solution 1

One of the possible solutions is to use recursion: find first open bracket, then continue until we have balance of brackets. When we found balance, run recursively function for left and for right subtrees. Complexity for balanced tree is O(n log n), for not balanced potentially can be O(n^2). In code I use fact, that ( has value 40 and ) has value 41.

Complexity

Time complexity can go upto O(n^2), space is O(n).

Code

class Solution:
    def str2tree(self, s):
        if not s: return None
        if '(' not in s:
            root = TreeNode(int(s))
            return root
        else:
            idx = s.index('(') + 1
            root = TreeNode(int(s[:idx - 1]))
            balance, start = 1, idx
   
            while balance:
                if s[idx] in "()": balance -= (2*ord(s[idx]) - 81)
                idx += 1
                
            root.left = self.str2tree(s[start:idx-1])
            root.right = self.str2tree(s[idx+1:-1])
            return root

Solution 2

Another, more difficult, but O(n) solution uses stack. Let us iterate over our string and if we found number, let us first construct it and create tree node. Then we attach this node as left or right children of parent: the last element of stack and add it to stack. Finally, if we meet ")", we remove node from stack.

Complexity

It is O(n).

Code

class Solution:
    def str2tree(self, s):
        stack, it = [], 0

        while it < len(s):
            if s[it] not in "()":
                num = s[it]
                while s[it+1].isdigit():
                    num += s[it+1]
                    it += 1
                curr = TreeNode(int(num))

                if stack:
                    parent = stack[-1]
                    if not parent.left:
                        parent.left = curr 
                    else:
                        parent.right = curr
                        
                stack.append(curr)

            if s[it] == ")": stack.pop()
            it += 1

        return stack[0]

Remark

We can create correspondences between open and closing brackets in O(n) using stack, like I did in 1896. Minimum Cost to Change the Final Value of Expression. Then we can use solution 1 and overall complexity will be O(n).