Leetcode 1028. Recover a Tree From Preorder Traversal

Gary Chiang
2 min readSep 3, 2021



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]


  • The number of nodes in the original tree is in the range [1, 1000].
  • 1 <= Node.val <= 109


  1. we will see dashes and value, so we verify it’s level and value while scan through the string
  2. because it’s in-order traversal, if the stack.size bigger than level, will pop out from the stack
  3. if the stack.peek().left is null, will add it into stack.peek().left; else add it into stack.peek().right
  4. to return the result, which is the root. We will need to pop all the other TreeNode in stack, until the last one -> the root
  5. Trick: use three variable in two for loops. Track index, level and value at the same time. Make sure index is not larger than string.length, to avoid overflow.



Gary Chiang

CS new grad, 6 years experience related to supply chain management. Located in Bay area