Binary TreesProblem 17 of 35
Construct Binary Tree from String with Bracket Representation
Problem Statement
Given a string representing a binary tree in bracket format, construct the binary tree. The format is: "root(left_subtree)(right_subtree)". A node can have 0, 1, or 2 children.
Example:
Input: "4(2(3)(1))(6(5))"
Output:
4
/ \
2 6
/ \ /
3 1 5
Input: "4(2(3)(1))(6(5)(7))"
Output:
4
/ \
2 6
/ \ / \
3 1 5 7
Approach 1: Recursive Parsing
Intuition
Parse the string character by character. When we see a number, create a node. When we see '(', recursively parse the subtree. When we see ')', return to parent.
Algorithm
- Extract the root value (could be negative or multi-digit)
- If '(' follows, recursively build left subtree
- If another '(' follows, recursively build right subtree
- Use an index pointer to track position in string
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int index;
private TreeNode buildTree(String s) {
if (index >= s.length()) return null;
// Parse the number (handle negative numbers)
int sign = 1;
if (s.charAt(index) == '-') {
sign = -1;
index++;
}
int num = 0;
while (index < s.length() && Character.isDigit(s.charAt(index))) {
num = num * 10 + (s.charAt(index) - '0');
index++;
}
TreeNode node = new TreeNode(sign * num);
// Check for left child
if (index < s.length() && s.charAt(index) == '(') {
index++; // Skip '('
node.left = buildTree(s);
index++; // Skip ')'
}
// Check for right child
if (index < s.length() && s.charAt(index) == '(') {
index++; // Skip '('
node.right = buildTree(s);
index++; // Skip ')'
}
return node;
}
public TreeNode str2tree(String s) {
if (s == null || s.isEmpty()) return null;
index = 0;
return buildTree(s);
}
}Complexity Analysis
- Time Complexity: O(n) - Each character is processed once
- Space Complexity: O(n) - Recursion stack in worst case (skewed tree)
Approach 2: Using Stack (Iterative)
Intuition
Use a stack to track parent nodes. When we see a number, create a node and attach it to the parent. '(' means go deeper, ')' means go back to parent.
Algorithm
- Use a stack to maintain the path from root to current node
- Parse numbers and create nodes
- '(' - expect a child next, attach to stack top
- ')' - finished with current subtree, pop from stack
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode str2treeIterative(String s) {
if (s == null || s.isEmpty()) return null;
Stack<TreeNode> stack = new Stack<>();
int i = 0;
while (i < s.length()) {
if (s.charAt(i) == ')') {
stack.pop();
i++;
} else if (s.charAt(i) == '(') {
i++;
} else {
// Parse number
int sign = 1;
if (s.charAt(i) == '-') {
sign = -1;
i++;
}
int num = 0;
while (i < s.length() && Character.isDigit(s.charAt(i))) {
num = num * 10 + (s.charAt(i) - '0');
i++;
}
TreeNode node = new TreeNode(sign * num);
// Attach to parent
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.push(node);
}
}
return stack.isEmpty() ? null : stack.peek();
}
}Complexity Analysis
- Time Complexity: O(n) - Each character processed once
- Space Complexity: O(n) - Stack can hold up to n/2 nodes
Bonus: Convert Tree Back to String
Key Takeaways
- Bracket format: "value(left)(right)" - parentheses wrap subtrees
- Key insight: First '(' after value is always left child
- Handle edge cases: Negative numbers, multi-digit numbers, missing children
- Recursive approach is cleaner but uses call stack
- Iterative approach with explicit stack avoids recursion limit
- This is LeetCode #536 - Construct Binary Tree from String
- Related: LeetCode #606 - Construct String from Binary Tree (reverse problem)