Construct Binary Tree from String - Solution & Explanation

Problem Overview: You are given a string representing a binary tree where integers denote node values and parentheses describe child relationships. Your task is to parse the string and reconstruct the corresponding binary tree structure. For example, "4(2(3)(1))(6(5))" represents a tree with root 4, left subtree rooted at 2, and right subtree rooted at 6.

Approach 1: Recursive DFS Parsing (O(n) time, O(n) space)

This method walks through the string and recursively builds nodes while tracking the current index. When you read digits (and possible minus signs), you form the node value. If the next character is (, you recursively construct the left child, and if another ( appears afterward, you construct the right child. Each recursive call consumes the portion of the string representing that subtree. Since every character is processed once, the time complexity is O(n). The recursion stack can grow to the tree height, giving O(n) worst-case space for skewed trees. This approach mirrors the natural structure of the tree and is easy to reason about during a depth-first search style reconstruction.

Approach 2: Stack-Based Iterative Construction (O(n) time, O(n) space)

The iterative approach processes the string left to right and uses a stack to maintain the current path of nodes. When you encounter a number, create a new node and attach it as the left child if the parent doesn't have one yet; otherwise attach it as the right child. Push the new node onto the stack. When a closing parenthesis ) appears, it signals the end of a subtree, so you pop the top node from the stack. This method avoids recursion and still visits each character exactly once, producing O(n) time complexity and O(n) auxiliary space for the stack.

The core challenge in this problem is parsing the string while maintaining the correct parent-child relationships in the binary tree. Both methods rely on recognizing that parentheses define subtree boundaries.

Recommended for interviews: The stack-based solution is often preferred because it avoids recursion depth issues and clearly shows how you track the current parent while parsing the string. However, implementing the recursive DFS parser first demonstrates strong understanding of tree structure and recursive decomposition. Most interviewers accept either approach as long as you achieve the optimal O(n) traversal and correctly parse multi-digit values.