536. Construct Binary Tree from String

Problem Description

The given problem requires constructing a binary tree from a string that is encoded to represent the structure of a binary tree. The string consists of integers and parentheses. An integer not enclosed in parentheses indicates the value of a node. A pair of parentheses following an integer contains the entirety of a child binary tree, structured in the same way with integers and parentheses. The string defines the values for nodes and the hierarchy of the nodes within the tree:

• If a node value is followed by a set of parentheses, the content within those parentheses represents the left child subtree.
• If there are two consecutive sets of parentheses following a node value, the first set describes the left child subtree, and the second describes the right child subtree.

We need to build the tree by starting with deciphering the value for the root node and then recursively constructing left and right subtrees according to the pattern found in the parentheses that follow each node value.

Intuition

To solve this problem, a Depth-First Search (DFS) strategy can be employed. The intuition behind using DFS is that the string representation of the tree broadly resembles a preorder traversal, where we start from the root and explore as far into each branch as possible before backtracking.

Here's the step-by-step thinking process:

1. Find the root value of the tree, which is the number sequence before the first parenthesis or at the beginning of the string if there are no parentheses.
2. Determine the boundaries of the left child subtree, which is encapsulated in the first pair of matching parentheses following the root value. Do this by keeping track of the count of parentheses.
3. Recursively construct the left subtree by applying the same process to the string between the first pair of matching parentheses.
4. If there's another pair of parentheses after the first one, it represents the right subtree. Similarly, determine its boundaries and recursively construct the right subtree using the same method.

Using this recursive DFS approach, we can construct subtrees from the inside out, and by attaching them to their respective parent nodes, we slowly build the entire binary tree represented by the given string.

The code provided defines a recursive function dfs which performs the above intuition steps, finding the root's value, then looking for left and right subtrees in the subsequent parentheses, constructing subtrees recursively, and connecting them to build the final binary tree.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The provided solution uses the recursive DFS strategy to parse the string and build the tree. The algorithm involves the following steps, which correspond to the intuitive steps we discussed:

1. Define a recursive function dfs that takes a string s as an input that represents the binary tree.

2. Check whether the input string is empty. If it is, return None, as it signifies the absence of a tree or subtree at this point.

3. Look for the first occurrence of a parenthesis in the string using s.find('('), which indicates the start of a child subtree.

4. If no parenthesis is found, it means the current string represents a leaf node, so create a TreeNode with its value and return it.

5. If a parenthesis is found, construct a TreeNode for the root from the integer before the parenthesis.

6. Use two counters:

   • start, to keep track of the opening parenthesis of the left child if we haven't processed it yet, or of the right child if we have.
   • cnt, to count the balance of opening and closing parentheses.

7. Iterate over the string starting from the index of the first parenthesis. For each character:

   • Increment cnt when an opening parenthesis ( is encountered.
   • Decrement cnt when a closing parenthesis ) is encountered.
   • When cnt reaches 0, it means we found a balanced pair of parentheses, indicating the end of a subtree definition.

8. Depending on whether we are processing the left or the right child based on the value of start, recursively call dfs on the substring within the found pair of parentheses (excluding the parentheses themselves) to construct the child subtree.

9. Once the left subtree is processed, adjust start to move to the next character after the closing parenthesis of the left subtree, which is either the opening parenthesis of the right subtree or the end of the string.

10. If there's another substring following the left subtree, it will be processed as the right subtree using the same recursive approach.

11. Return the root node with its left and right children attached accordingly.

The dfs function is then called with the entire string and the constructed tree is returned. This effectively parses and constructs the binary tree in a depth-first manner from the string representation.

1class Solution:
2    def str2tree(self, s: str) -> TreeNode:
3        def dfs(s):
4            if not s:
5                return None
6            p = s.find('(')
7            if p == -1:
8                return TreeNode(int(s))
9            root = TreeNode(int(s[:p]))
10            start = p
11            cnt = 0
12            for i in range(p, len(s)):
13                if s[i] == '(':
14                    cnt += 1
15                elif s[i] == ')':
16                    cnt -= 1
17                if cnt == 0:
18                    if start == p:
19                        root.left = dfs(s[start + 1 : i])
20                        start = i + 1
21                    else:
22                        root.right = dfs(s[start + 1 : i])
23            return root
24
25        return dfs(s)

This approach makes use of recursion for tree construction and is efficient in terms of space as no extra data structure is needed besides the input string and the tree nodes themselves. It ensures that nodes are correctly assigned to their parent nodes, properly constructing the binary tree from the string.

Example Walkthrough

Let's take an example string "4(2(3)(1))(6(5))" to illustrate the solution approach step by step.

1. The recursive function dfs starts with the full string "4(2(3)(1))(6(5))".

2. It identifies 4 as the root because it's before the first parenthesis.

3. It then creates a TreeNode with value 4.

4. Since 4 is followed by parentheses, it looks for the left subtree starting at the first opening parenthesis.

5. cnt is used to keep track of parentheses balance. Starting with start at the index of ( following the 4.

6. It finds the matching closing parenthesis for the left subtree at the index right after 1), which makes 2(3)(1) as the substring for the left subtree.

7. A recursive call dfs("2(3)(1)") is made to construct the left subtree:

   7.1. The function identifies 2 as the root of this subtree. 7.2. It then encounters 3 within the first pair of parentheses, indicating a left child. Therefore, it creates a TreeNode with value 3 and attaches it to the left of 2. 7.3. Next, it finds 1 in the second pair of parentheses, constructs a TreeNode with value 1, and attaches it to the right of 2.

8. With the left subtree completed, the function now looks for the right subtree. It sets start to the character index right after the left subtree, which is )( before 6.

9. As there is a substring 6(5) after the first subtree, it calls dfs("6(5)") to construct the right subtree:

   9.1. The subtree root is 6, identified before the opening parenthesis. 9.2. Inside the parentheses 5, it indicates a left child for the 6 node. Hence, it creates a TreeNode with 5 and attaches it to the left of 6.

10. No more parentheses follow the 6(5) substring, signifying there is no right child for the 6 node.

11. Now the right subtree is also constructed with the root 6 and its left child 5 attached.

12. Finally, the function returns the full tree. The 4 node has its left child as the subtree rooted at 2 with children 3 and 1. Its right child is the subtree rooted at 6 with a left child 5.

The final binary tree structure from the example "4(2(3)(1))(6(5))" will be as follows:

1    4
2   / \
3  2   6
4 / \ /
53  1 5

By using the recursive dfs function and following the vowels of paired parentheses, this approach systematically constructs each node's correct tree position according to the input string representation.

Solution Implementation

Time and Space Complexity

The given Python code defines a recursive function to construct a binary tree from a string representation. The function dfs scans the string character by character to find the left and right subtree for each node.

Time Complexity:

The worst-case time complexity of the function is O(n^2). This is because, for every recursive call to dfs, a substring operation (s[start + 1 : i]) is performed, which can take O(n) time in the worst case. Since the function iterates over every character in the string with a length of n, the total time complexity would be O(n * n) for the worst case where you have many nested parentheses, causing many recursive calls and substrings operations.

Space Complexity:

The space complexity is also O(n) in the worst case. This is due to the recursive nature of dfs which may go as deep as the length of the string in the case of a completely skewed tree (a tree where every node only has one child). Additionally, each recursive call may create a substring which takes up additional space, but since Python strings are immutable and string slicing creates a new copy, the space taken by these temporary slices shouldn't add to the space complexity caused by the call stack—the space complexity remains bounded by O(n) due to the call stack size in recursion.

Learn more about how to find time and space complexity quickly using problem constraints.