Recover a Tree From Preorder Traversal solution and explanation
Google
9 more videos on this problem
Recover a Tree From Preorder Traversal - Leetcode 1028 - PythonNeetCodeIO · 19:40 · 11K views
Recover a Tree From Preorder Traversal | Easy DFS Simulation | Leetcode 1028 | codestorywithMIKcodestorywithMIK · 26:46 · 10K views
Recover a Tree From Preorder Traversal | Leetcode 1028Techdose · 19:41 · 4K views
LeetCode 1028 Recover a Tree From Preorder Traversalleetuition · 17:36 · 4K views
1028. Recover a Tree From Preorder Traversal | Stack | Binary TreeAryan Mittal · 18:27 · 2K views
Leetcode Hard: 1028. Recover a Tree From Preorder Traversalleetcode · 12:23 · 1K views
1028. Recover a Tree From Preorder Traversal (Leetcode Hard)Programming Live with Larry · 15:14 · 872 views
1028. Recover a Tree From Preorder Traversal - Daily Leetcode (Day 44)yeetcode · 12:05 · 240 views
LeetCode 1028 Recover a Tree From Preorder Traversal | Tree | Asked in Google Amazon MetaCode Harmony · 26:50 · 181 views
Leetcode 1028. Recover a Tree From Preorder Traversal (stack)LetsCode · 18:19 · 95 views
The problem
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:
- The number of nodes in the original tree is in the range
[1, 1000]. 1 <= Node.val <= 109
Approach overview
Problem 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 1: Recursive Approach
In this approach, we recursively parse the traversal string to construct the tree. We track the current position in the string and the expected depth using recursion. For each valid node, we create a new tree node and attempt to construct its left and right subtrees by increasing the expected depth.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def recoverFromPreorder(traversal: str) -> TreeNode:
def helper(pos, depth):
nonlocal index
if index >= len(traversal):
return None
num_dashes = 0
while index + num_dashes < len(traversal) and traversal[index + num_dashes] == '-':
num_dashes += 1
if num_dashes != depth:
return None
index += num_dashes
start = index
while index < len(traversal) and traversal[index].isdigit():
index += 1
value = int(traversal[start:index])
node = TreeNode(value)
node.left = helper(depth + 1)
node.right = helper(depth + 1)
return node
index = 0
return helper(0)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
int pos;
public TreeNode recoverFromPreorder(String S) {
pos = 0;
return dfs(S, 0);
}
private TreeNode dfs(String str, int depth) {
int numDashes = 0;
while (pos + numDashes < str.length() && str.charAt(pos + numDashes) == '-') {
numDashes++;
}
if (depth != numDashes) return null;
pos += numDashes;
int start = pos;
while (pos < str.length() && Character.isDigit(str.charAt(pos))) {
pos++;
}
int val = Integer.parseInt(str.substring(start, pos));
TreeNode node = new TreeNode(val);
node.left = dfs(str, depth + 1);
node.right = dfs(str, depth + 1);
return node;
}
}#include <string>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* recoverFromPreorder(std::string traversal) {
int pos = 0;
return dfs(traversal, pos, 0);
}
TreeNode* dfs(const std::string &traversal, int &pos, int depth) {
int numDashes = 0;
while (pos + numDashes < traversal.size() && traversal[pos + numDashes] == '-')
numDashes++;
if (numDashes != depth) return nullptr;
pos += numDashes;
int startPos = pos;
while (pos < traversal.size() && isdigit(traversal[pos]))
pos++;
int val = std::stoi(traversal.substr(startPos, pos - startPos));
TreeNode *node = new TreeNode(val);
node->left = dfs(traversal, pos, depth + 1);
node->right = dfs(traversal, pos, depth + 1);
return node;
}The code defines a TreeNode class and a recoverFromPreorder function that constructs a binary tree from the given traversal string. This is done using a nested helper function that recursively builds the tree. The function uses a nonlocal index variable to maintain the current position within the string.
For each node, helper checks the number of dashes to see if they match the expected depth. If they match, it extracts the number representing the node's value, creates a TreeNode, and attempts to add left and right children by increasing the expected depth.
Time Complexity: O(n), where n is the length of the traversal string, since each character is processed once.
Space Complexity: O(h), where h is the height of the tree, as this is the maximum depth of the recursion stack.
Approach 2: Iterative Approach Using Stack
An iterative approach can be implemented using a stack. We use the stack to keep track of nodes along with their depths, and iteratively add nodes while maintaining the correct parent-child relationships. Each new node is inserted as a child of the node on the top of the stack, with adjustments made based on depths.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def recoverFromPreorder(traversal: str) -> TreeNode:
stack = []
index = 0
while index < len(traversal):
level = 0
while index < len(traversal) and traversal[index] == '-':
level += 1
index += 1
value = 0
while index < len(traversal) and traversal[index].isdigit():
value = value * 10 + int(traversal[index])
index += 1
node = TreeNode(value)
while len(stack) > level:
stack.pop()
if stack and stack[-1].left is None:
stack[-1].left = node
elif stack:
stack[-1].right = node
stack.append(node)
return stack[0]function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var recoverFromPreorder = function(traversal) {
let stack = [];
let index = 0;
while (index < traversal.length) {
let level = 0;
while (index < traversal.length && traversal[index] === '-') {
level++;
index++;
}
let value = 0;
while (index < traversal.length && !isNaN(traversal[index])) {
value = value * 10 + (traversal[index] - '0');
index++;
}
let node = new TreeNode(value);
while (stack.length > level) {
stack.pop();
}
if (stack.length > 0) {
if (!stack[stack.length - 1].left) {
stack[stack.length - 1].left = node;
} else {
stack[stack.length - 1].right = node;
}
}
stack.push(node);
}
return stack[0];
};public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode RecoverFromPreorder(string traversal) {
Stack<TreeNode> stack = new Stack<TreeNode>();
int pos = 0;
while (pos < traversal.Length) {
int level = 0;
while (pos < traversal.Length && traversal[pos] == '-') {
level++;
pos++;
}
int val = 0;
while (pos < traversal.Length && char.IsDigit(traversal[pos])) {
val = val * 10 + (traversal[pos] - '0');
pos++;
}
TreeNode node = new TreeNode(val);
while (stack.Count > level) {
stack.Pop();
}
if (stack.Count != 0) {
if (stack.Peek().left == null) {
stack.Peek().left = node;
} else {
stack.Peek().right = node;
}
}
stack.Push(node);
}
while (stack.Count > 1) stack.Pop();
return stack.Pop();
}
}In Python, an iterative solution uses a stack to manage nodes and depths while parsing the traversal string. The number of dashes determines the depth. Nodes are created based on parsed values, and the stack is leveraged to attach each node at the correct position in the tree. Levels deeper than the current node's depth are popped from the stack, associating nodes as the left (and subsequently right) child of the last valid node at that depth.
Time Complexity: O(n), where n is the string length, as each character is evaluated once.
Space Complexity: O(h), where h is the height of the tree, related to the maximum size of the stack.
Approach 3: Default Approach
function recoverFromPreorder(traversal: string): TreeNode | null {
const stack: TreeNode[] = [];
let i = 0;
while (i < traversal.length) {
let depth = 0;
while (i < traversal.length && traversal[i] === '-') {
depth++;
i++;
}
let num = 0;
while (i < traversal.length && !Number.isNaN(+traversal[i])) {
num = num * 10 + +traversal[i];
i++;
}
// Create the new node
const newNode = new TreeNode(num);
while (stack.length > depth) {
stack.pop();
}
if (stack.length > 0) {
const i = stack.length - 1;
if (stack[i].left === null) {
stack[i].left = newNode;
} else {
stack[i].right = newNode;
}
}
stack.push(newNode);
}
return stack.length ? stack[0] : null;
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n), where n is the length of the traversal string, since each character is processed once. Space Complexity: O(h), where h is the height of the tree, as this is the maximum depth of the recursion stack. |
| Iterative Approach Using Stack | Time Complexity: O(n), where n is the string length, as each character is evaluated once. Space Complexity: O(h), where h is the height of the tree, related to the maximum size of the stack. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Recover a Tree From Preorder Traversal easy or hard?
Recover a Tree From Preorder Traversal is classified as a Hard problem because it combines string parsing with binary tree reconstruction. The challenge comes from correctly interpreting depth markers and maintaining parent-child relationships while preserving preorder structure.
Recover a Tree From Preorder Traversal Python/Java solution
Python, Java, and C++ solutions typically implement either recursive DFS parsing or an iterative stack approach. Both parse the traversal string to determine node depth and value, then connect nodes accordingly. The stack-based version is concise and widely used in Python and Java implementations.
How to solve Recover a Tree From Preorder Traversal in O(n)?
Parse the string sequentially while counting dashes to determine node depth and reading the numeric value that follows. Use a stack to track the current root-to-node path. Pop until the stack size matches the parent depth, attach the new node as a left or right child, and push it onto the stack. This processes every node once, achieving O(n) time.
What is the best approach for Recover a Tree From Preorder Traversal?
The stack-based iterative approach is generally the best choice. It scans the preorder string once, determines node depth from dash counts, and uses a stack to maintain the path from root to the current node. Each node is pushed and popped at most once, giving O(n) time complexity with O(n) auxiliary space.
Is Recover a Tree From Preorder Traversal asked at Google/Amazon/Meta?
Tree reconstruction and preorder parsing problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that combine tree traversal with stack or DFS parsing are common because they test both string processing and binary tree construction skills.
What data structure is used in Recover a Tree From Preorder Traversal?
A stack is commonly used to track the path from the root to the current node during reconstruction. The algorithm also relies on binary tree node structures and preorder traversal properties. Some solutions instead use recursion with a DFS parsing strategy.
What is the time complexity of Recover a Tree From Preorder Traversal?
The optimal solutions run in O(n) time where n is the length of the traversal string. Each character is processed once to determine node depth and value. Stack operations or recursive calls also occur at most once per node, keeping the algorithm linear.