Recover a Tree From Preorder Traversal

Explore how to reconstruct a binary tree from a preorder traversal string by applying depth-first search methods. Understand how node depth and child positioning affect tree structure and practice implementing a clear solution to recover the tree efficiently.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

We perform a preorder depth-first traversal on a binary tree starting from its root.

For each node, we first write D dashes, where D is the depth of the node in the tree, followed by the node’s integer value.
The root node has depth 0.
If a node is at depth D, its children (if any) will appear at depth D + 1.
If a node has only one child, it will always be the left child.

You are given the string representation of this traversal. Your task is to reconstruct the original binary tree and return its root. ...