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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

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

1class Solution:
2    def str2tree(self, s: str) -> TreeNode:
3        """
4        Converts a string representation of a binary tree into a binary tree
5        structure and returns the root node of the tree.
6      
7        :param s: String that represents a binary tree where:
8                  - An integer wrapped in parenthesis "()" represents a node.
9                  - Nested parenthesis represent children nodes, where the first
10                    set of parenthesis encloses the left child and the second
11                    set encloses the right child.
12                  Example: "4(2(3)(1))(6(5))"
13        :return: Tree root node.
14        """
15
16        def build_tree(string):
17            """
18            Recursive helper function to build the tree from the string.
19
20            :param string: A substring of the original tree string.
21            :return: The constructed TreeNode.
22            """
23            if not string:  # If the string is empty, return None (no node).
24                return None
25          
26            # Find the first parenthesis to separate the node value from children.
27            paren_index = string.find('(')
28            if paren_index == -1:  # No parenthesis found, meaning no children.
29                return TreeNode(int(string))  # Return node with the given value.
30              
31            # The value of the node is up to the first parenthesis.
32            root = TreeNode(int(string[:paren_index]))
33          
34            balance = 0  # Keeps track of the balance of parenthesis.
35            start = paren_index  # Start of the substring for child nodes.
36
37            # Iterate through the string starting from the first '('.
38            for i in range(paren_index, len(string)):
39                char = string[i]
40                if char == '(':
41                    balance += 1
42                elif char == ')':
43                    balance -= 1
44
45                # When balance is 0, we know a set of parenthesis is closed.
46                if balance == 0:
47                    if start == paren_index:
48                        # The content within the first set of parenthesis
49                        # pertains to the left child.
50                        root.left = build_tree(string[start + 1:i])
51                        start = i + 1  # Move to the potential next child.
52                    else:
53                        # Content within the second set of parenthesis
54                        # pertains to the right child.
55                        root.right = build_tree(string[start + 1:i])
56
57            # Return the constructed node with its connected children.
58            return root
59
60        # Start the tree building with the entire string.
61        return build_tree(s)
62
1class Solution {
2    /**
3     * Converts a string representing a binary tree into the tree itself.
4     *
5     * @param s the string representing a binary tree
6     * @return the root node of the binary tree
7     */
8    public TreeNode str2tree(String s) {
9        return parseTree(s);
10    }
11
12    /**
13     * Helper method to deep first search the string and construct the binary tree.
14     *
15     * @param s the string representing a binary tree
16     * @return a TreeNode representing the current node being processed
17     */
18    private TreeNode parseTree(String s) {
19        // Return null for an empty string
20        if ("".equals(s)) {
21            return null;
22        }
23
24        // Find the position of the first left parenthesis
25        int leftParenIndex = s.indexOf("(");
26      
27        // If no parenthesis is found, only a number is present, so create a lone node
28        if (leftParenIndex == -1) {
29            return new TreeNode(Integer.parseInt(s));
30        }
31
32        // Create the root node with the value before the first parenthesis
33        TreeNode root = new TreeNode(Integer.parseInt(s.substring(0, leftParenIndex)));
34
35        // Keep track of the parenthesis balance
36        int balance = 0;
37      
38        // Tracks the start position for the substring to process next
39        int subStart = leftParenIndex;
40      
41        for (int i = leftParenIndex; i < s.length(); i++) {
42            // Update balance when a parenthesis is encountered
43            if (s.charAt(i) == '(') {
44                balance++;
45            } else if (s.charAt(i) == ')') {
46                balance--;
47            }
48
49            // When balance becomes zero, we have a balanced subpart of the string
50            if (balance == 0) {
51                if (subStart == leftParenIndex) {
52                    // This substring corresponds to the left child
53                    root.left = parseTree(s.substring(subStart + 1, i));
54                    // Update the start position for the right child
55                    subStart = i + 1;
56                } else {
57                    // This substring corresponds to the right child, if present
58                    root.right = parseTree(s.substring(subStart + 1, i));
59                }
60            }
61        }
62        // Return the root node of the subtree created
63        return root;
64    }
65}
66
1#include <string>
2using namespace std;
3
4// Definition for a binary tree node.
5struct TreeNode {
6    int val;
7    TreeNode *left;
8    TreeNode *right;
9    TreeNode() : val(0), left(nullptr), right(nullptr) {}
10    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
12};
13
14class Solution {
15public:
16    TreeNode* str2tree(string s) {
17        return dfs(s);
18    }
19
20    // Helper function to recursively construct a binary tree from a string
21    TreeNode* dfs(string s) {
22        // If the string is empty, return nullptr as we have reached the end 
23        // of the string parse or it maps to an empty subtree
24        if (s.empty()) return nullptr;
25
26        // Find the first occurrence of "(" which signifies the start of a child subtree
27        size_t parenthesesPos = s.find("(");
28      
29        // If no "(" found, this means the current node is a leaf node
30        if (parenthesesPos == string::npos) return new TreeNode(stoi(s));
31
32        // Construct a new tree node from the number before the first "("
33        TreeNode* rootNode = new TreeNode(stoi(s.substr(0, parenthesesPos)));
34      
35        int balance = 0; // Variable to keep track of balanced parentheses
36        int childStartPos = parenthesesPos; // The start position of the child subtree string
37      
38        // Loop to process the content within the parentheses
39        for (int i = parenthesesPos; i < s.size(); ++i) {
40            if (s[i] == '(')
41                ++balance;
42            else if (s[i] == ')')
43                --balance;
44          
45            // When we encounter balanced parentheses, we are at the end of a subtree
46            if (balance == 0) {
47                // The left child subtree
48                if (childStartPos == parenthesesPos) {
49                    rootNode->left = dfs(s.substr(childStartPos + 1, i - childStartPos - 1));
50                    childStartPos = i + 1;
51                } 
52                // The right child subtree
53                else {
54                    rootNode->right = dfs(s.substr(childStartPos + 1, i - childStartPos - 1));
55                }
56            }
57        }
58        // Return the constructed binary tree node with its left and/or right subtrees
59        return rootNode;
60    }
61};
62
1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    constructor(val: number = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14// Function to convert a string to a binary tree.
15function str2tree(s: string): TreeNode | null {
16    return dfs(s);
17}
18
19// Helper function to recursively construct a binary tree from a string.
20function dfs(s: string): TreeNode | null {
21    // If the string is empty, return null which signifies either the end of parsing,
22    // or that it corresponds to an empty subtree.
23    if (s === "") return null;
24
25    // Find the first occurrence of '(' which indicates the start of a child subtree.
26    const parenthesesPos: number = s.indexOf("(");
27
28    // If '(' is not found, this implies that the current node is a leaf node.
29    if (parenthesesPos === -1) return new TreeNode(parseInt(s));
30
31    // Construct a new TreeNode from the number before the first '('
32    const rootNode = new TreeNode(parseInt(s.substring(0, parenthesesPos)));
33
34    // Variables to keep track of balanced parentheses and child subtree string positions.
35    let balance = 0;
36    let childStartPos = parenthesesPos;
37
38    // Loop through the string and process the contents within the parentheses.
39    for (let i = parenthesesPos; i < s.length; i++) {
40        if (s[i] === '(') balance += 1;
41        else if (s[i] === ')') balance -= 1;
42
43        // When balance is zero, we have reached the end of a subtree.
44        if (balance === 0) {
45            // Determine if the substring is for the left or right child subtree
46            if (childStartPos === parenthesesPos) {
47                rootNode.left = dfs(s.substring(childStartPos + 1, i));
48                // Update position for the start of the potential right child subtree
49                childStartPos = i + 1;
50            } else {
51                rootNode.right = dfs(s.substring(childStartPos + 1, i));
52            }
53        }
54    }
55
56    // Return the newly constructed TreeNode with its left and/or right subtrees.
57    return rootNode;
58}
59

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄