Recover a Tree From Preorder Traversal

Recover a Tree From Preorder Traversal

What is this problem about?

The Recover a Tree From Preorder Traversal problem gives you a preorder traversal string encoding of a binary tree where dashes (—) indicate the depth. Parse this string to reconstruct the tree. This hard coding problem uses DFS with a stack to parse depth-encoded nodes. The DFS, string, binary tree, and tree interview pattern is the core.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this because it tests tree construction from a serialization format — a skill relevant to data persistence and network transmission. The depth-stack parsing is a clean DFS construction approach.

Algorithmic pattern used

DFS with depth stack. Parse the string left to right. For each node: count leading dashes (= depth), parse the number after dashes. Maintain a stack representing the current path from root. Pop the stack until its size equals the current node's depth, then attach as the left or right child of stack[-1]. Push current node.

Example explanation

s="1-2--3---4-5--6---7".

• "1" depth=0: root=1. Stack=[1].
• "-2" depth=1: left child of 1. Stack=[1,2].
• "--3" depth=2: left child of 2. Stack=[1,2,3].
• "---4" depth=3: left child of 3. Stack=[1,2,3,4].
• "-5" depth=1: pop until size=1. Right child of 1. Stack=[1,5]. ...Result: tree with root 1.

Common mistakes candidates make

• Not handling the right child correctly (second child added after popping to correct depth).
• Confusing depth with number of dashes (count carefully).
• Off-by-one in pop condition.
• Not resetting the pointer correctly after parsing each number.

Interview preparation tip

Tree reconstruction from depth-encoded strings uses a depth-indexed stack. The stack always contains the path from root to the current deepest node. When encountering a new node at depth d, pop the stack until depth == d (the parent is now at the top). Practice tree serialization/deserialization in multiple formats: preorder with nulls, level-order, depth-encoded.