Construct Binary Tree from String

To construct a binary tree from a string consisting of parentheses and integers, we can use a recursive approach. The given string represents the pre-order traversal of the tree, and we’ll parse the string accordingly to build the binary tree.

Here’s a Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def str2tree(self, s: str) -> Optional[TreeNode]:
        # If the string is empty, return None
        if not s:
            return None

        # Index to keep track of current position in the string
        index = 0

        # Helper function to parse the integer value
        def parseValue(s):
            nonlocal index
            sign = 1
            if s[index] == '-':
                sign = -1
                index += 1
            value = 0
            while index < len(s) and s[index].isdigit():
                value = value * 10 + int(s[index])
                index += 1
            return sign * value

        # Recursive function to construct the tree
        def buildTree():
            nonlocal index
            if index >= len(s) or s[index] == ')':
                return None

            value = parseValue(s)
            node = TreeNode(value)

            # If there is a left child, recurse
            if index < len(s) and s[index] == '(':
                index += 1
                node.left = buildTree()
                index += 1 # Skip closing parenthesis

            # If there is a right child, recurse
            if index < len(s) and s[index] == '(':
                index += 1
                node.right = buildTree()
                index += 1 # Skip closing parenthesis

            return node

        return buildTree()

Explanation:

  1. Parse Value: The helper function parseValue is used to parse an integer value (with a possible negative sign) from the string and update the current index.
  2. Recursive Tree Construction: The recursive function buildTree constructs the tree by reading the root value, followed by optional left and right subtrees enclosed in parentheses.
  3. Process the String: We call the buildTree function to process the entire string and construct the binary tree.

This code will construct and return the binary tree represented by the given string s.