Is Recover a Tree From Preorder Traversal easy or hard?

Recover a Tree From Preorder Traversal is classified as a Hard problem because it combines string parsing with binary tree reconstruction. The challenge comes from correctly interpreting depth markers and maintaining parent-child relationships while preserving preorder structure.

Recover a Tree From Preorder Traversal Python/Java solution

Python, Java, and C++ solutions typically implement either recursive DFS parsing or an iterative stack approach. Both parse the traversal string to determine node depth and value, then connect nodes accordingly. The stack-based version is concise and widely used in Python and Java implementations.

How to solve Recover a Tree From Preorder Traversal in O(n)?

Parse the string sequentially while counting dashes to determine node depth and reading the numeric value that follows. Use a stack to track the current root-to-node path. Pop until the stack size matches the parent depth, attach the new node as a left or right child, and push it onto the stack. This processes every node once, achieving O(n) time.

What is the best approach for Recover a Tree From Preorder Traversal?

The stack-based iterative approach is generally the best choice. It scans the preorder string once, determines node depth from dash counts, and uses a stack to maintain the path from root to the current node. Each node is pushed and popped at most once, giving O(n) time complexity with O(n) auxiliary space.

Is Recover a Tree From Preorder Traversal asked at Google/Amazon/Meta?

Tree reconstruction and preorder parsing problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that combine tree traversal with stack or DFS parsing are common because they test both string processing and binary tree construction skills.

What data structure is used in Recover a Tree From Preorder Traversal?

A stack is commonly used to track the path from the root to the current node during reconstruction. The algorithm also relies on binary tree node structures and preorder traversal properties. Some solutions instead use recursion with a DFS parsing strategy.

What is the time complexity of Recover a Tree From Preorder Traversal?

The optimal solutions run in O(n) time where n is the length of the traversal string. Each character is processed once to determine node depth and value. Stack operations or recursive calls also occur at most once per node, keeping the algorithm linear.

Description Hints 1 Solution Video 19:40

1028. Recover a Tree From Preorder Traversal

Hard83.2% acceptance6 companies

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]

Constraints:

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

Asked at 6 companies

Grammarly

Google Amazon Microsoft Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Do an iterative depth first search, parsing dashes from the string to inform you how to link the nodes together.

19:40

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

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

Input

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

Input

"1-401--349---90--88"

Your code is saved on this device.Solution