Tap here to switch tabs
Problem
Submissions

Problem: Recover a Tree From Preorder Traversal

Recover a Tree From Preorder Traversal gives you a preorder string where dashes show each node's depth. Reconstruct the original binary tree and return its root; a lone child is always left.

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.

Constraints:

  • The number of nodes in the original binary tree lies within the range [1,500][1, 500].

  • 1≤1 \leq node.data ≤103\leq 10^3

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Recover a Tree From Preorder Traversal

Recover a Tree From Preorder Traversal gives you a preorder string where dashes show each node's depth. Reconstruct the original binary tree and return its root; a lone child is always left.

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.

Constraints:

  • The number of nodes in the original binary tree lies within the range [1,500][1, 500].

  • 1≤1 \leq node.data ≤103\leq 10^3