Watch 10 video solutions for Construct String from Binary Tree, a medium level problem involving String, Tree, Depth-First Search. This walkthrough by NeetCode has 41,724 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root node of a binary tree, your task is to create a string representation of the tree following a specific set of formatting rules. The representation should be based on a preorder traversal of the binary tree and must adhere to the following guidelines:
Node Representation: Each node in the tree should be represented by its integer value.
Parentheses for Children: If a node has at least one child (either left or right), its children should be represented inside parentheses. Specifically:
Omitting Empty Parentheses: Any empty parentheses pairs (i.e., ()) should be omitted from the final string representation of the tree, with one specific exception: when a node has a right child but no left child. In such cases, you must include an empty pair of parentheses to indicate the absence of the left child. This ensures that the one-to-one mapping between the string representation and the original binary tree structure is maintained.
In summary, empty parentheses pairs should be omitted when a node has only a left child or no children. However, when a node has a right child but no left child, an empty pair of parentheses must precede the representation of the right child to reflect the tree's structure accurately.
Example 1:
Input: root = [1,2,3,4] Output: "1(2(4))(3)" Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".
Example 2:
Input: root = [1,2,3,null,4] Output: "1(2()(4))(3)" Explanation: Almost the same as the first example, except the()after2is necessary to indicate the absence of a left child for2and the presence of a right child.
Constraints:
[1, 104].-1000 <= Node.val <= 1000Problem Overview: Given a binary tree, build a string using preorder traversal where each node is written as value(left)(right). Empty parentheses are omitted unless needed to preserve the one‑to‑one mapping between the string and the tree structure.
Approach 1: Recursive Tree Traversal (DFS) (Time: O(n), Space: O(h))
The most natural solution uses preorder depth‑first traversal. Visit the current node, append its value to the result string, then recursively process the left and right children. The tricky rule: if a node has a right child but no left child, you must add an empty pair () to represent the missing left subtree. This preserves the structure so the tree can be uniquely reconstructed. Every node is processed once, giving O(n) time complexity. The recursion stack stores at most the tree height h, so the auxiliary space is O(h). This approach directly mirrors the definition of preorder traversal in a binary tree and is the most concise implementation.
Approach 2: Iterative Approach Using Stack (Time: O(n), Space: O(n))
An iterative version simulates DFS using an explicit stack. Push the root node and process nodes in preorder order while building the string. Track visited nodes so you know when to append closing parentheses. When pushing children, push the right child first and the left child second so the left subtree is processed first. If a node has a right child but no left child, explicitly append () before handling the right subtree. Each node enters and leaves the stack once, so the runtime remains O(n). The stack may hold multiple nodes simultaneously, leading to O(n) worst‑case space.
This problem mainly tests understanding of preorder depth‑first search and careful handling of string construction. Managing parentheses correctly is the core challenge rather than the traversal itself. The resulting algorithm builds the string incrementally while traversing the tree.
Recommended for interviews: The recursive DFS approach is what interviewers usually expect. It shows you understand preorder traversal and edge cases like missing left children when a right child exists. Mentioning the iterative stack version demonstrates deeper knowledge of how recursion can be simulated and how DFS works internally.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Tree Traversal (DFS) | O(n) | O(h) | Best general solution. Clean and concise when recursion depth is manageable. |
| Iterative DFS Using Stack | O(n) | O(n) | Useful when avoiding recursion or when stack‑based DFS is preferred. |