How to Solve Recover a Tree From Preorder Traversal

Start by parsing the preorder string and tracking the number of dashes to determine node depth. Use a stack to manage the current path of ancestors and link children correctly, ensuring left-child priority when only one child exists. This method handles the depth-first traversal sequence accurately and builds the tree in O(n) time while maintaining the proper parent-child hierarchy.

Problem Statement

Given a string representing the preorder traversal of a binary tree, each node value is preceded by D dashes where D is its depth. The root node has depth 0, and for any node, its children appear immediately after it in the string, with their depth equal to the parent's depth plus one. If a node has only one child, it is always the left child.

Your task is to reconstruct the original binary tree from this traversal string. Return the tree as a standard binary tree structure or as an array representing level-order traversal with null placeholders for missing children. The traversal string contains only digits and dashes, and all node values are positive integers.

Examples

Example 1

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

Output: [1,2,5,3,4,6,7]

Example details omitted.

Example 2

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

Output: [1,2,5,3,null,6,null,4,null,7]

Example details omitted.

Example 3

Input: traversal = "1-401--349---90--88"

Output: [1,401,null,349,88,90]

Example details omitted.

Constraints

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

Solution Approach

Iterative Parsing with Depth Tracking

Scan the string character by character to extract node values and count leading dashes to determine depth. Maintain a stack of nodes representing the current path from the root to the latest node. Pop nodes from the stack until the top node's depth is one less than the new node's depth, then attach the new node as the left or right child accordingly and push it onto the stack.

Handle Single-Child Nodes

If a node has only one child, guarantee it is linked as the left child. The depth tracking ensures that when a new node appears at depth D+1, it is attached to the correct parent. This avoids misplacement errors where the child could be incorrectly assigned as right or skipped entirely.

Time and Space Optimization

The algorithm processes each character exactly once and each node is pushed and popped at most once from the stack, giving O(n) time complexity. Using a stack to track ancestors provides O(n) space usage, which is necessary to correctly manage node hierarchy and depth relations during reconstruction.

Complexity Analysis

Time complexity is O(n) because we parse each character and node once. Space complexity is O(n) due to the stack holding up to all nodes along a path, which is essential to reconstruct the tree correctly.

What Interviewers Usually Probe

• Ask if the candidate handles single-child nodes correctly as left children.
• Check if the solution correctly counts dashes to determine node depth.
• Watch for proper use of a stack or similar structure to maintain current ancestors.

Common Pitfalls or Variants

Common pitfalls

• Miscounting dashes and attaching nodes to the wrong parent depth.
• Assuming right children when a node has only one child, breaking tree structure.
• Pushing all nodes onto the stack without popping ancestors, leading to incorrect hierarchy.

Follow-up variants

• Recover tree from a preorder string with variable-length integers and missing children indicated explicitly.
• Construct a tree from a preorder sequence where some nodes may be skipped or null explicitly.
• Recover a binary tree while returning the result as a nested dictionary instead of array representation.

How GhostInterview Helps

• Automatically parses traversal strings and manages depth tracking to build the tree structure correctly.
• Highlights stack-based iterative DFS approach and warns about common mislinking errors with single-child nodes.
• Provides immediate validation against example outputs to ensure reconstructed tree matches the intended preorder sequence.

Topic Pages

• String
• Tree
• Depth-First Search
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What does 'Recover a Tree From Preorder Traversal' mean in practice?

It means reconstructing a binary tree from a string where node values are prefixed with dashes indicating their depth, restoring the original parent-child relationships.

Why is depth tracking necessary for this problem?

Depth tracking ensures each new node is attached to the correct parent, especially when handling single-child nodes, maintaining the proper binary tree hierarchy.

Can this be solved recursively instead of iteratively?

Yes, recursion can track depth naturally, but an iterative stack-based approach often reduces call stack overhead and aligns with preorder traversal parsing.

What is the time complexity of reconstructing the tree?

The reconstruction runs in O(n) time, processing each character and node once, while correctly managing the depth-to-parent relationships.

How are single-child nodes handled in this reconstruction?

Any node with only one child is guaranteed to have it as the left child, so the algorithm attaches it accordingly based on the depth sequence.