Recover a Tree From Preorder Traversal
01 · Problem
A binary tree was written out as a single string by a preorder DFS. For each node, the writer emitted D dashes, where D is the node's depth (the root has depth 0), immediately followed by the node's value. Nothing separates one node from the next except the dashes.
If a node has exactly one child, that child is always its left child.
Given the string traversal, rebuild the tree and return its root. The output is the tree in level-order form, with null for missing children and trailing nulls removed.
02 · Examples
traversal = "1-2--3---4-5"
[1,2,5,3,null,null,null,4]
Node 1 is the root. 2 (depth 1) is its left child, 3 (depth 2) is 2's left child, 4 (depth 3) is 3's left child, and 5 (depth 1) is the root's right child.
traversal = "1-2--3--4-5--6--7"
[1,2,5,3,4,6,7]
2 and 5 are the children of 1; 3 and 4 are the children of 2; 6 and 7 are the children of 5.
traversal = "10-7--3-20"
[10,7,20,3]
7 is the left child of 10, 3 is the left child of 7, and 20 returns to depth 1 as the right child of 10.
03 · Constraints
- 01The number of nodes in the tree is in the range [1, 1000].
- 021 <= Node.val <= 109
- 03traversal is a valid encoding of some binary tree using only digits and '-'.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.