LeetCode 1028: Recover a Tree From Preorder Traversal

Problem Restatement

We run a preorder depth-first traversal on a binary tree.

At each node, we output its depth (as a count of dashes) followed by its value.

For example, a tree with root 1 and left child 2 and right child 5 would produce "1-2--3--4-5--6--7" for a specific tree.

We are given this string traversal and need to recover the original binary tree.

The official constraints state that the number of nodes is in [1, 1000], 1 <= Node.val <= 10^9.

Input and Output

Function shape:

def recoverFromPreorder(traversal: str) -> Optional[TreeNode]:
    ...

Examples

Example 1:

traversal = "1-2--3--4-5--6--7"

Recovered tree:

      1
     / \
    2   5
   / \ / \
  3  4 6  7

Key Insight

Use a stack where position depth holds the most recently created node at that depth.

Parse the string to extract (depth, value) pairs.

For each pair, create a new node. If the stack has a node at depth - 1, attach the new node as a left child (if no left child yet) or right child.

Since preorder visits left before right, the left child is always filled first.

After placing the new node, truncate the stack to depth depth + 1 so future siblings overwrite it.

Algorithm

1. Parse the traversal string into (depth, value) pairs.
2. Maintain a stack where stack[d] is the most recent node at depth d.
3. For each (depth, value):
   • Create node = TreeNode(value).
   • If depth > 0, attach to stack[depth - 1] as left child (if empty) or right child.
   • Set stack[depth] = node (or extend the stack).
4. Return stack[0].

Correctness

In preorder, a node is visited before its children. The depth tells us which level the node belongs to. The first child of a node is always its left child (preorder visits left subtree first).

By maintaining one node per depth level in the stack, we correctly track which parent to attach each new node to.

Edge Cases

• A missing child should not contribute a fake value to min/max or path computations.
• Leaf nodes often define the base case; verify the behavior on a single-node tree.
• When passing state down the tree, update it before visiting children that depend on the current node.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from typing import Optional

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        stack = []
        i = 0
        n = 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)

            if depth < len(stack):
                stack = stack[:depth]

            if stack:
                parent = stack[-1]
                if parent.left is None:
                    parent.left = node
                else:
                    parent.right = node

            stack.append(node)

        return stack[0]

Code Explanation

Parse depth by counting leading dashes:

while i < n and traversal[i] == '-':
    depth += 1
    i += 1

Parse the integer value:

while i < n and traversal[i].isdigit():
    val = val * 10 + int(traversal[i])
    i += 1

Truncate the stack to the current depth (removing deeper nodes from previous branches):

if depth < len(stack):
    stack = stack[:depth]

Attach to the parent (the top of the trimmed stack):

if parent.left is None:
    parent.left = node
else:
    parent.right = node

Testing

def preorder_vals(root):
    if not root:
        return []
    return [root.val] + preorder_vals(root.left) + preorder_vals(root.right)

def run_tests():
    s = Solution()
    assert preorder_vals(s.recoverFromPreorder("1-2--3--4-5--6--7")) == [1, 2, 3, 4, 5, 6, 7]
    assert preorder_vals(s.recoverFromPreorder("1-2--3---4-5--6---7")) == [1, 2, 3, 4, 5, 6, 7]
    assert preorder_vals(s.recoverFromPreorder("1-401--349---90--88")) == [1, 401, 349, 90, 88]
    print("all tests passed")

run_tests()