Recover a Tree From Preorder Traversal: Stack-Based Tree Construction

Given a string that represents a preorder traversal of a binary tree, recover the original tree and return its root. In the string, dashes before each number indicate the node's depth. The root has zero dashes, its children have one dash, their children have two dashes, and so on. Each node that has only one child is guaranteed to have a left child.

This is LeetCode 1028: Recover a Tree From Preorder Traversal.

Example: The string "1-2--3--4-5--6--7" encodes a tree rooted at 1, with left subtree rooted at 2 (children 3 and 4) and right subtree rooted at 5 (children 6 and 7).

Why this problem matters

This problem tests two skills at once: parsing structured text and building a tree from that parsed data. You need to extract meaningful tokens (depth and value) from a flat string, then use those tokens to reconstruct a hierarchical structure. These are the same skills you use when writing a parser, deserializing data, or processing any depth-encoded format.

The parsing half forces you to manage an index into the string carefully. You cannot just split on dashes because multi-digit numbers and varying dash counts make the format irregular. The construction half forces you to think about how depth relates to parent-child relationships, and how a stack can track your position in the tree as you process nodes in preorder.

If you can solve this problem cleanly, you have a solid grasp of stack-based tree construction, which shows up in many tree serialization and deserialization problems.

The key insight

Use a stack to maintain the current path from the root down to the most recently added node. As you parse each token (a depth and a value), compare the depth to the current stack size. If the depth equals the stack size, the new node is the left child of the node on top of the stack. If the depth is smaller, pop nodes off the stack until its size matches the depth, then attach the new node as the right child of the new top.

This works because preorder traversal visits nodes in the order: root, left subtree, right subtree. When the depth increases by one, you are going deeper into the left subtree. When the depth stays the same or decreases, you have finished a subtree and are now adding a right child (or moving back up to add a right child of an ancestor).

The solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def recoverFromPreorder(traversal):
    stack = []
    i = 0
    while i < len(traversal):
        depth = 0
        while i < len(traversal) and traversal[i] == '-':
            depth += 1
            i += 1

        value = 0
        while i < len(traversal) and traversal[i].isdigit():
            value = value * 10 + int(traversal[i])
            i += 1

        node = TreeNode(value)

        while len(stack) > depth:
            stack.pop()

        if stack:
            if not stack[-1].left:
                stack[-1].left = node
            else:
                stack[-1].right = node

        stack.append(node)

    return stack[0]

Here is what each piece does:

• The outer while i < len(traversal) loop processes one node per iteration, advancing i through the string.
• The first inner loop counts consecutive dashes to determine the depth of the next node.
• The second inner loop reads consecutive digits to build the node's value. This handles multi-digit numbers correctly.
• while len(stack) > depth pops nodes until the stack size matches the target depth. This "rewinds" the path back to the correct parent.
• After popping, the top of the stack is the parent. If the parent has no left child yet, the new node goes left. Otherwise, it goes right.
• stack.append(node) pushes the new node, extending the current path deeper.
• stack[0] is always the root, so you return it at the end.

Visual walkthrough

Notice how the stack grows when depth increases (going left) and shrinks when depth decreases (backtracking to attach a right child). Each pop discards a completed subtree, and the stack top always points to the correct parent for the next node.

Complexity analysis

Time is O(n) where n is the length of the input string. You scan each character exactly once: once when counting dashes and once when reading digits. Each node is pushed and popped from the stack at most once, so the stack operations add O(m) total work where m is the number of nodes. Since m is at most n, the total is O(n).

Space is O(h) where h is the height of the tree. The stack holds at most h + 1 nodes at any point (the path from root to the current node). In the worst case (a left-skewed tree), h = m - 1 where m is the total number of nodes. For a balanced tree, h = O(log m).

The building blocks

1. String parsing with index tracking

The parsing pattern here is a manual scan with an index variable i that advances through the string. You alternate between two modes: counting dashes and reading digits. This is more reliable than using split() or regex because the delimiter (dashes) and the data (digits) have variable lengths and no consistent separator.

depth = 0
while i < len(traversal) and traversal[i] == '-':
    depth += 1
    i += 1

value = 0
while i < len(traversal) and traversal[i].isdigit():
    value = value * 10 + int(traversal[i])
    i += 1

This two-phase scan pattern appears in many string parsing problems. The key discipline is always checking i < len(traversal) before accessing traversal[i], and making sure i advances in every branch so you never loop infinitely.

2. Stack-based tree construction

The stack tracks the current path from root to the deepest node processed so far. When you encounter a node at a given depth, you pop until the stack size equals that depth, then attach the new node as a child of the top element.

while len(stack) > depth:
    stack.pop()

if stack:
    if not stack[-1].left:
        stack[-1].left = node
    else:
        stack[-1].right = node

stack.append(node)

This is the same pattern used in problems where you reconstruct a tree from a serialized format. The stack acts as a "breadcrumb trail" that lets you backtrack to the right parent without recursion. It works because preorder traversal guarantees that left children appear before right children, so the first time you attach a child it goes left, and the second time it goes right.

Edge cases

• Single node. The string is just a number with no dashes, like "1". Depth is 0, the node becomes the root, and you return it immediately.
• Left-skewed tree. Every node has only a left child. The string looks like "1-2--3---4". The stack grows with each node and never pops, because depth always increases by one.
• Multi-digit node values. A string like "10-20--300" must be parsed correctly. The digit-reading loop handles this by accumulating value = value * 10 + int(traversal[i]).
• Deep tree (many dashes). If the tree has height 1000, the string has tokens prefixed by 1000 dashes. The algorithm handles this naturally because it just counts dashes in a loop.
• Right child after deep left subtree. After processing a long chain of left children, the depth suddenly drops. The stack pops many elements at once to find the correct parent. This is the trickiest scenario and the one that makes a stack necessary.

From understanding to recall

You just traced through the full algorithm: scan dashes for depth, scan digits for value, pop the stack until it matches the depth, attach the new node as left or right child, and push. The stack invariant (stack size equals the current depth plus one) is the thread that holds everything together.

But reading through the walkthrough once is not the same as being able to reproduce it. Under time pressure, will you remember to pop before attaching? Will you recall the left-before-right rule? Will you handle multi-digit numbers without a bug?

Spaced repetition locks these details in. You write the solution from scratch at increasing intervals, and each time, the parsing loop, the stack logic, and the child-attachment rule become more automatic. After a few rounds, the pattern is something you recall rather than re-derive.

Related posts

• Serialize and Deserialize Binary Tree - tree serialization and reconstruction
• Construct Binary Tree from Preorder and Inorder Traversal - building trees from traversal data
• Verify Preorder Serialization of a Binary Tree - validating preorder structure

CodeBricks breaks problems like Recover a Tree From Preorder Traversal into the building blocks behind them, then uses spaced repetition to make those blocks automatic. If you want to stop re-solving the same patterns and start recognizing them on sight, give it a try.