Problem overview
A binary tree is written as a string in preorder: a node, then its whole left subtree, then its whole right subtree. Before each value there are as many dashes as the node's depth, with the root at depth 0 and no dashes. A node with a single child always has it on the left. The method RecoverFromPreorder receives that string, traversal, and returns the root of the rebuilt TreeNode tree.
In "1-2--3--4-5--6--7", the node 1 is the root. The values 2 and 5 have one dash, so they are its children, with 2 on the left because it comes first. The two nodes after 2 have two dashes, so they are the children of 2, and the two after 5 are the children of 5. Read level by level, the tree is [1, 2, 5, 3, 4, 6, 7].
Values can have several digits, as in "5-12--7---40--9". Here 5 has only the child 12, on its left, 12 has the children 7 and 9, and 7 has one child, 40. Read level by level, the tree is [5, 12, null, 7, 9, 40].
Approach: keep the path from the root to the newest node
Preorder always writes a node right after its parent's earlier nodes, so the parent of a new node is on the path from the root to the node just written. A stack can hold exactly that path: the node at position d of the stack has depth d.
For every node read, with depth d and a value:
- Drop nodes from the top of the stack until it holds exactly
dnodes. What is left is the path down to depthd - 1, and its top is the new node's parent. - If the parent has no left child yet, attach the new node there. Otherwise attach it on the right. Preorder writes the left subtree first, so the first child is the left one, and a parent has at most two children.
- Push the new node. It may be the parent of the next one.
The nodes that were dropped are finished: their subtrees are complete, and they stay attached to their own parents. The stack is only a bookmark for finding parents.
Here is "1-2--3---4-5--6---7", where the depth falls from 3 to 1 at once:
| Depth | Value | Stack after the node is pushed | Where it is attached |
|---|---|---|---|
| 0 | 1 | 1 | root |
| 1 | 2 | 1, 2 | left of 1 |
| 2 | 3 | 1, 2, 3 | left of 2 |
| 3 | 4 | 1, 2, 3, 4 | left of 3 |
| 1 | 5 | 1, 5 | right of 1 |
| 2 | 6 | 1, 5, 6 | left of 5 |
| 3 | 7 | 1, 5, 6, 7 | left of 6 |
When 5 arrives at depth 1, the stack 1, 2, 3, 4 is cut down to its first node, 1. Node 1 already has the left child 2, so 5 goes to the right.
Step by step
- Create the stack as an empty
List<TreeNode>namedstack.Addpushes at the end, and the top is the last element. - Create
i, the position intraversal, starting at 0. The string is read once, left to right. - Loop while
i < traversal.Length. Each pass reads one node. - Start
depthat 0 for this node. - Count the dashes with a loop that runs while
traversal[i] == '-'. - Inside it, increase
depthand moveiforward. When it stops,iis on the first digit. - Start
valueat 0. The number is built digit by digit. - Read the digits with a loop that runs while
iis inside the string and the character is not a dash. - Append each digit:
value = value * 10 + (traversal[i] - '0'), then movei. Reading 4 then 0 gives 4, then 40. - Create the node with
new TreeNode(value). - Cut the stack with a loop that runs while
stack.Count > depth. - Remove the top with
RemoveAt(stack.Count - 1). - Check that the stack is not empty. Only the root finds it empty, since it is the only node at depth 0.
- Name the parent: the last element,
stack[stack.Count - 1]. It stays on the stack because it may get a second child. - Attach on the left if
parent.leftis stillnull. - Otherwise attach on the right.
- Push the node with
Add. - Return
stack[0]. The root is never removed, because every other node has depth 1 or more and so never cuts the stack below one node.
The solution in C#
class Solution {
public TreeNode RecoverFromPreorder(string traversal) {
List<TreeNode> stack = new List<TreeNode>();
int i = 0;
while (i < traversal.Length) {
int depth = 0;
while (traversal[i] == '-') {
depth++;
i++;
}
int value = 0;
while (i < traversal.Length && traversal[i] != '-') {
value = value * 10 + (traversal[i] - '0');
i++;
}
TreeNode node = new TreeNode(value);
while (stack.Count > depth) {
stack.RemoveAt(stack.Count - 1);
}
if (stack.Count > 0) {
TreeNode parent = stack[stack.Count - 1];
if (parent.left == null) {
parent.left = node;
} else {
parent.right = node;
}
}
stack.Add(node);
}
return stack[0];
}
}
The C# details worth knowing:
- Indexing a string gives a
char.traversal[i]is a character, so it is compared with a character literal in single quotes,'-'. A double-quoted"-"would be a string, and the comparison would not compile. - Digit characters to numbers. Subtracting two
chars gives anintin C#, so'7' - '0'is the number 7. The digit characters have consecutive codes, which is what makes this work. - The order of the two conditions matters. In
i < traversal.Length && traversal[i] != '-', the bounds check comes first, sotraversal[i]is never read past the end. Reading outside a string throws anIndexOutOfRangeException. The dashes loop has no bounds check, because a valid traversal never ends with a dash. - A
Listas a stack.RemoveAton the last index removes the top without shifting anything. AStack<T>would do for popping, but the code also needsstack.Countto equal the depth andstack[0]to reach the root, and the list does both. - Nodes are references. Setting
parent.left = nodelinks the object itself. Later removing it from theListdoesn't affect the tree. - Values fit in an
int. The largest value is 1,000,000,000, below theintmaximum of 2,147,483,647, and building it digit by digit never goes past it.
Complexity
Let n be the length of traversal.
Time: O(n). Each character is read once. Each node is pushed once and removed at most once, so all the stack operations together are proportional to the number of nodes, which is at most n.
Space: O(h) besides the tree. The stack holds one path, so its size is the height of the tree, at most the number of nodes. The tree itself takes O(n) memory, as the answer.
Edge cases and common mistakes
- A single node.
"1"reads depth 0, finds the stack empty, pushes the node and returns it:[1]. - A single child goes left.
"1-2"gives[1, 2], with 2 on the left of 1. The attach rule does this on its own, because the first child of any parent goes left. - A chain.
"1-2--3---4----5"gives[1, 2, null, 3, null, 4, null, 5]: every node is the left child of the previous one. - A big jump up. In
"1-2--3---4-5"the depth falls from 3 to 1, and the cutting loop removes three nodes from the stack in a single pass. - Two children.
"1-2-3"gives[1, 2, 3]. Node 2 is cut off when 3 arrives at depth 1, and 3 becomes the right child because 1 already has a left child. - Multi-digit values. Reading one character per node would split
12into 1 and 2. The digits loop keeps reading until the next dash. - Counting dashes as digits. Treating a dash as part of a number breaks the depth count. The dashes loop must end on the first digit.
- Cutting the stack to
depth - 1. The loop leavesdepthnodes on the stack, so that the top is the parent at depthdepth - 1. Keeping one more would attach a node to its own sibling. - Popping the parent after attaching a child. A parent may still need a second child, so it stays until a shallower node cuts it off.
Testing
"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]."1"gives[1]."1-2-3"gives[1, 2, 3]."1-401--349---90--88"gives[1, 401, null, 349, 88, 90].
