Watch 10 video solutions for Recover a Tree From Preorder Traversal, a hard level problem involving String, Tree, Depth-First Search. This walkthrough by NeetCodeIO has 10,916 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We run a preorder depth-first search (DFS) on the root of a binary tree.
At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.
If a node has only one child, that child is guaranteed to be the left child.
Given the output traversal of this traversal, recover the tree and return its root.
Example 1:
Input: traversal = "1-2--3--4-5--6--7" Output: [1,2,5,3,4,6,7]
Example 2:
Input: traversal = "1-2--3---4-5--6---7" Output: [1,2,5,3,null,6,null,4,null,7]
Example 3:
Input: traversal = "1-401--349---90--88" Output: [1,401,null,349,88,90]
Constraints:
[1, 1000].1 <= Node.val <= 109Problem Overview: The input string represents a preorder traversal of a binary tree where node depth is encoded using dashes (-). Each node value appears after a sequence of dashes equal to its depth. Your task is to rebuild the original binary tree from this encoded preorder string.
Approach 1: Recursive Parsing with DFS (Time: O(n), Space: O(h))
This method parses the string while recursively building the tree in preorder order. First read the number of dashes to determine the node’s depth, then parse the integer value that follows. If the current depth matches the expected depth, create the node and recursively build its left and right children. If the dash count does not match the expected depth, backtrack so the parent call can attach the node correctly. The traversal naturally mirrors preorder construction using depth-first search. Time complexity is O(n) because each character in the string is processed once, and space complexity is O(h) due to the recursion stack where h is tree height.
Approach 2: Iterative Construction Using Stack (Time: O(n), Space: O(n))
The iterative approach processes the string left to right and uses a stack to track the path from root to the current node. First count dashes to determine the node depth, then parse the node value. While the stack size is greater than the current depth, pop nodes until the parent at depth d-1 remains on top. Attach the new node as the left child if empty, otherwise as the right child. Push the new node onto the stack to maintain the traversal path. The stack effectively represents the current root-to-node path in the tree. Each node is pushed and popped at most once, giving O(n) time and O(n) auxiliary space.
Recommended for interviews: The stack-based iterative approach is typically expected in interviews because it directly models the preorder traversal path and avoids complex recursion state management. The recursive solution demonstrates strong understanding of preorder parsing and DFS construction, but the stack version is easier to reason about under time pressure while maintaining the optimal O(n) runtime.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS Parsing | O(n) | O(h) | Good when recursion is comfortable and you want code that mirrors preorder traversal logic |
| Iterative Stack Construction | O(n) | O(n) | Preferred in interviews; stack explicitly tracks node depth and parent relationships |