Construct Binary Tree From String - Leetcode Solution

Problem Statement: 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, the first parenthesis pair denotes the left subtree and the second parenthesis pair denotes the right subtree.

Each of the sub-tree follows the same structure i.e. an integer followed by zero, one or two pairs of parenthesis.

The input string is always valid and doesn't contain any extra spaces.

Example: Input: "4(2(3)(1))(6(5))" Output: 4 /
2 6 / \ / 3 1 5

Solution: The given problem can be solved using a recursive approach. We can use two pointers to keep track of the current node and the end of the node's value in the string. Whenever we encounter an opening parenthesis, we know that the next node will be the left child of the current node. Similarly, when we encounter a closing parenthesis, we know that the current node has no more children.

Let's go through the steps to solve the problem.

1. Define the TreeNode structure: A TreeNode represents each node in a binary tree and it contains three fields - the value of the node and two pointers to the left and right children.

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

2. Define a recursive function called str2tree which takes a string s as input and returns the root node of the binary tree.

def str2tree(s: str) -> TreeNode:

3. Check if the given input string s is empty. If it is empty, return None.

    if not s:
        return None

4. Define two helper functions inorder, which takes a string s and an integer index and returns the index of the next closing parenthesis in the string, and evalNode, which takes a string s, a start index i and an end index j and returns the corresponding TreeNode.

    def inorder(s, i):
        j = i
        count = 0
        while j < len(s):
            if s[j] == '(':
                count += 1
            elif s[j] == ')':
                count -= 1
                if count == 0:
                    return j
            j += 1

    def evalNode(s, i, j):
        val = ''
        neg = 1
        if s[i] == '-':
            neg = -1
            i += 1
        while i <= j:
            val += s[i]
            i += 1
        node = TreeNode(int(val) * neg)
        return node

5. We will first create the root node using evalNode and then recursively create the left and right children by calling the same function again. The index to start searching for the next child is the index of the next closing parenthesis of the current child + 1.

    # Find the index of the first closing parenthesis and create the root node
    i = 0
    j = inorder(s, i)
    root = evalNode(s, i, j)

    # Check if there are any children
    if j == len(s) - 1:
        return root

    # Find index of the start of left subtree and right subtree
    i = j + 1
    j = inorder(s, i)

    root.left = str2tree(s[i:j+1])

    if j == len(s) - 1:
        return root

    i = j + 1
    j = len(s) - 1

    root.right = str2tree(s[i:j+1])

    return root

6. Finally, call the str2tree function with the input string and return the root node.

s = "4(2(3)(1))(6(5))"
root = str2tree(s)

7. Now, we can print the tree to ensure that it is created correctly.

def printTree(root: TreeNode):
    if not root:
        return
    print(root.val)
    printTree(root.left)
    printTree(root.right)

printTree(root)
# Output: 
# 4
# 2
# 3
# 1
# 6
# 5

1