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.
Flowchart Walkthrough
To determine the appropriate algorithm for the problem described in LeetCode 536. Construct Binary Tree from String, let’s utilize the algorithm flowchart to guide our decision-making process. Here's an in-depth exploration using the Flowchart:
Is it a graph?
- Yes: Though this problem is about constructing a binary tree, a tree is a type of graph without cycles and with a single root.
Is it a tree?
- Yes: The main structure to be formed is a binary tree, where each node has up to two children.
Following the designated paths on the flowchart after affirming it is a tree leads directly to:
DFS (Depth-First Search)
- Appropriate choice for problems where tree construction or traversal is involved, especially when handling hierarchical breakdowns of the string resembling serialized tree structures.
Therefore, based on the parameters of LeetCode 536 and following the structured guidance of the flowchart, DFS is recommended to recursively parse the string and construct the binary tree accordingly. This method efficiently navigates through the string, partitioning it based on nested parentheses which represent different tree nodes, perfectly aligning with the DFS approach of exploring as deep as possible along each branch before backtracking.
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:
- 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.
- 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.
- Recursively construct the left subtree by applying the same process to the string between the first pair of matching parentheses.
- 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:
-
Define a recursive function
dfs
that takes a strings
as an input that represents the binary tree. -
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. -
Look for the first occurrence of a parenthesis in the string using
s.find('(')
, which indicates the start of a child subtree. -
If no parenthesis is found, it means the current string represents a leaf node, so create a
TreeNode
with its value and return it. -
If a parenthesis is found, construct a
TreeNode
for the root from the integer before the parenthesis. -
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.
-
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.
- Increment
-
Depending on whether we are processing the left or the right child based on the value of
start
, recursively calldfs
on the substring within the found pair of parentheses (excluding the parentheses themselves) to construct the child subtree. -
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. -
If there's another substring following the left subtree, it will be processed as the right subtree using the same recursive approach.
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example string "4(2(3)(1))(6(5))"
to illustrate the solution approach step by step.
-
The recursive function
dfs
starts with the full string"4(2(3)(1))(6(5))"
. -
It identifies
4
as the root because it's before the first parenthesis. -
It then creates a
TreeNode
with value4
. -
Since
4
is followed by parentheses, it looks for the left subtree starting at the first opening parenthesis. -
cnt
is used to keep track of parentheses balance. Starting withstart
at the index of(
following the4
. -
It finds the matching closing parenthesis for the left subtree at the index right after
1)
, which makes2(3)(1)
as the substring for the left subtree. -
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 encounters3
within the first pair of parentheses, indicating a left child. Therefore, it creates aTreeNode
with value3
and attaches it to the left of2
. 7.3. Next, it finds1
in the second pair of parentheses, constructs aTreeNode
with value1
, and attaches it to the right of2
. -
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)(
before6
. -
As there is a substring
6(5)
after the first subtree, it callsdfs("6(5)")
to construct the right subtree:9.1. The subtree root is
6
, identified before the opening parenthesis. 9.2. Inside the parentheses5
, it indicates a left child for the6
node. Hence, it creates aTreeNode
with5
and attaches it to the left of6
. -
No more parentheses follow the
6(5)
substring, signifying there is no right child for the6
node. -
Now the right subtree is also constructed with the root
6
and its left child5
attached. -
Finally, the function returns the full tree. The
4
node has its left child as the subtree rooted at2
with children3
and1
. Its right child is the subtree rooted at6
with a left child5
.
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.
How many times is a tree node visited in a depth first search?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.