Recover a Tree From Preorder Traversal
Problem
We run a preorder DFS on a binary tree and output each node as a number, prefixed by D dashes, where D is the node's depth (the root has depth 0). Given that string traversal, reconstruct and return the binary tree. If a node has only one child, it is guaranteed to be the left child.
traversal = "1-2--3--4-5--6--7"[1, 2, 5, 3, 4, 6, 7]def recoverFromPreorder(traversal):
stack = []
i, n = 0, len(traversal)
while i < n:
depth = 0
while i < n and traversal[i] == '-':
depth += 1
i += 1
val = 0
while i < n and traversal[i].isdigit():
val = val * 10 + int(traversal[i])
i += 1
node = TreeNode(val)
while len(stack) > depth:
stack.pop()
if stack:
parent = stack[-1]
if parent.left is None:
parent.left = node
else:
parent.right = node
stack.append(node)
return stack[0]function recoverFromPreorder(traversal) {
const stack = [];
let i = 0, n = traversal.length;
while (i < n) {
let depth = 0;
while (i < n && traversal[i] === '-') { depth++; i++; }
let val = 0;
while (i < n && traversal[i] >= '0' && traversal[i] <= '9') {
val = val * 10 + (traversal[i] - '0'); i++;
}
const node = { val, left: null, right: null };
while (stack.length > depth) stack.pop();
if (stack.length) {
const parent = stack[stack.length - 1];
if (parent.left === null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
return stack[0];
}class Solution {
public TreeNode recoverFromPreorder(String traversal) {
Deque<TreeNode> stack = new ArrayDeque<>();
int i = 0, n = traversal.length();
while (i < n) {
int depth = 0;
while (i < n && traversal.charAt(i) == '-') { depth++; i++; }
int val = 0;
while (i < n && Character.isDigit(traversal.charAt(i))) {
val = val * 10 + (traversal.charAt(i) - '0'); i++;
}
TreeNode node = new TreeNode(val);
while (stack.size() > depth) stack.pop();
if (!stack.isEmpty()) {
TreeNode parent = stack.peek();
if (parent.left == null) parent.left = node;
else parent.right = node;
}
stack.push(node);
}
TreeNode root = null;
while (!stack.isEmpty()) root = stack.pop();
return root;
}
}TreeNode* recoverFromPreorder(string traversal) {
vector<TreeNode*> stack;
int i = 0, n = traversal.size();
while (i < n) {
int depth = 0;
while (i < n && traversal[i] == '-') { depth++; i++; }
int val = 0;
while (i < n && isdigit(traversal[i])) {
val = val * 10 + (traversal[i] - '0'); i++;
}
TreeNode* node = new TreeNode(val);
while ((int)stack.size() > depth) stack.pop_back();
if (!stack.empty()) {
TreeNode* parent = stack.back();
if (parent->left == nullptr) parent->left = node;
else parent->right = node;
}
stack.push_back(node);
}
return stack.front();
}Explanation
The string is a preorder dump where the number of leading dashes tells you a node's depth. The trick is to keep a stack that always holds the current path from the root down to the node we just placed.
We scan the string token by token. For each token we count the dashes to get depth, then read the digits to get val and make a node.
Before attaching the new node, we pop the stack until its size equals depth. That leaves the correct parent on top — exactly the node one level above ours on the current path. We attach the new node as the parent's left child if that slot is empty, otherwise as the right child. Then we push the new node so it becomes the deepest node on the path.
Example: in "1-2--3", we push 1 (depth 0). Token 2 has depth 1, parent is 1, attach as left, push. Token 3 has depth 2; the stack is [1, 2], size already 2, so parent is 2 and 3 becomes its left child.
Because the problem guarantees a lone child is always the left one, the "left first, else right" rule is always correct. Each token is handled once, giving a linear-time rebuild.