Problem overview
A binary tree is written in preorder: a node, then its whole left subtree, then its whole right subtree. Each node is written as D dashes followed by its value, where D is the node's depth. The root has depth 0, so it has no dashes. If a node has only one child, that child is the left one.
The method recoverFromPreorder receives the string traversal and returns the root of the rebuilt tree. Values are between 1 and 1,000,000,000, so they can have several digits, and the input is always a valid traversal.
For "1-2--3--4-5--6--7" the nodes are 1 (depth 0), 2 (1), 3 (2), 4 (2), 5 (1), 6 (2) and 7 (2). Node 2 is the first child of the root, so it's the left child. 3 and 4 follow it one level deeper, so they are its children. 5 is back at depth 1, a second child of the root, so it's the right child, and 6 and 7 belong to it. The tree is [1,2,5,3,4,6,7] in level order.
Approach: keep the path from the root
Preorder order has a useful property: after a node comes its subtree, and the next node written at a lower depth belongs to some node on the path from the root to the last node. So the string can be read once, from left to right, while keeping a stack that holds that path. The node at position d of the stack has depth d.
When a new node with depth depth is read, its parent is the node at depth depth - 1. Nodes deeper than that are finished, because their subtrees ended when the depth dropped. So pop the stack until it holds exactly depth nodes. The top is then the parent.
The new node is attached as the parent's left child if that is still empty, and as the right child otherwise. This works because preorder writes the left subtree first, so a parent's first child is always its left one, which also matches the rule for a node with a single child. Finally the new node is pushed, since it is now the deepest node of the path.
On "1-2--3---4-5--6---7", after reading 4 the stack is 1, 2, 3, 4. Then 5 arrives with depth 1, so the stack is cut down to just 1. The root has a left child already, so 5 becomes its right child. The depth went back up by two levels at once, and the stack handles that without special cases.
Step by step
- Create
stackas an empty array. It will hold the path from the root down to the last node read. - Create
i, starting at 0. It is the position being read intraversal. Every loop that reads a character advances it, so the string is read once. - Write the main
while (i < traversal.length)loop. Each pass reads one node: its dashes, then its value. - Create
depth, starting at 0, to count the dashes of this node. - Loop while
traversal[i] === '-'. No bounds check is needed because the string never ends with a dash: a value always follows. - In that loop, add one to
depthand advancei. When it stops,iis on the first digit. - Create
value, starting at 0, to build the number digit by digit. - Loop while
iis inside the string andtraversal[i]is not a dash. A value ends at the next node's dashes or at the end of the string. - Update the value: multiply by 10 and add
Number(traversal[i]), then advancei. Reading 4 and then 0 gives 4, then 4 * 10 + 0 = 40. - Create
nodeas anew TreeNode(value). - Drop the finished nodes: while
stack.length > depth, pop. Afterwards the stack holds the path down to depthdepth - 1, and its top is the parent. - Pop the top inside that loop. The popped nodes stay attached to their own parents; they just can't get new children.
- Check
stack.length > 0. Only the root, the first node read, finds the stack empty, because it is the only node at depth 0. - Name the top
parent, the element at indexstack.length - 1. It stays on the stack because it may get a second child later. - If
parent.leftisnull, setparent.lefttonode. A first child is a left child. - Otherwise set
parent.righttonode. A parent has at most two children, and the second goes on the right. - Push
nodeonto the stack. The stack again holds the path from the root to the newest node. - After the loop, return
stack[0]. The root is the first node read and is never popped, because every other node has depth 1 or more and so leaves at least the root on the stack.
The solution in JavaScript
class Solution {
recoverFromPreorder(traversal) {
let stack = [];
let i = 0;
while (i < traversal.length) {
let depth = 0;
while (traversal[i] === '-') {
depth++;
i++;
}
let value = 0;
while (i < traversal.length && traversal[i] !== '-') {
value = value * 10 + Number(traversal[i]);
i++;
}
let node = new TreeNode(value);
while (stack.length > depth) {
stack.pop();
}
if (stack.length > 0) {
let parent = stack[stack.length - 1];
if (parent.left === null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.push(node);
}
return stack[0];
}
}Some details about JavaScript:
- Strings can be indexed.
traversal[i]is a one-character string. Reading past the end givesundefined, which is not equal to'-'. That is why the dash loop needs no bounds check, while the digit loop checksi < traversal.lengthto be explicit. Number('4')converts one digit. The digit loop only sees characters that aren't dashes, which in a valid input are digits.Number('-')would giveNaN, which is why the dashes are consumed before the digits.- Values fit in a double exactly. The largest value, 1,000,000,000, is far below 2 to the power 53, so building it with
value * 10 + digitloses nothing. parent.left === nullworks becauseTreeNodesets both children tonull. A missing child isnull, notundefined.
Complexity
Every character of the string is read once. Each node is pushed once and popped at most once, so the stack work is O(n) overall, where n is the number of nodes. The total time is O(L), where L is the length of the string. The stack holds one path, so the extra space is O(h) for a tree of height h, on top of the tree itself.
Edge cases and common mistakes
- Multi-digit values. Reading one character as a whole value would split
12into 1 and 2. In"5-12--7---40--9"the values 12 and 40 have two digits each. - A node with one child. The child goes on the left. For
"5-12--7---40--9", the root 5 has only 12, as its left child, and the tree is[5,12,null,7,9,40]in level order. - The depth jumps back several levels. The
whileloop that pops handles any number of levels, where a singlepop()would only handle one. - A single-node string.
"7"has depth 0 and an empty stack, so the node is pushed and returned as the root with no children. - Popping the parent. Pop only while
stack.length > depth. Popping one more would remove the parent, and the second child would be attached to the wrong node.
Testing
The method returns these trees, shown in level order with trailing nulls left out:
"1-2--3--4-5--6--7"gives[1,2,5,3,4,6,7]."1-2--3---4-5--6---7"gives[1,2,5,3,null,6,null,4,null,7]."5-12--7---40--9"gives[5,12,null,7,9,40]."7"gives[7].
