Recover From Preorder Traversal

Problem Statement

You are given a string representing the preorder depth-first search (DFS) traversal of a binary tree. In this traversal, each node is output as a series of dashes followed by its integer value. The number of dashes indicates the node's depth in the tree:

• The root node (depth 0) is printed without any dashes.
• For any node at depth D, its children are printed with D+1 leading dashes.
• Note: If a node has only one child, it is guaranteed to be the left child.

Your task is to reconstruct the original binary tree from this traversal string and return the tree's root.

---

Task

Implement a function that, given the preorder traversal string, recovers the binary tree and returns its root.

---

Test Cases

Example 1

Input:
traversal = "10-20--30--40-50--60--70" Output:
[10, 20, 50, 30, 40, 60, 70]

Explanation:

• The root is 10.
• 20 is the left child of 10.
• 30 and 40 are the left and right children of 20, respectively.
• 50 is the right child of 10.
• 60 and 70 are the left and right children of 50, respectively.

---

Example 2

Input:
traversal = "8-9--10---11-12--13---14" [8, 9, 12, 10, null, 13, null, 11, null, 14] Explanation:

• The root is 8.
• 9 is the left child of 8.
• 10 is the left child of 9.
• 11 is the left child of 10.
• 12 is the right child of 8.
• 13 is the left child of 12.
• 14 is the left child of 13.

---

Example 3

Input:
traversal = "100-200--300---400---500-600--700" Output: [100, 200, 600, 300, null, 700, null, 400, 500]

Explanation:

• The root is 100.
• 200 is the left child of 100.
• 300 is the left child of 200.
• 400 and 500 are the left and right children of 300, respectively.
• 600 is the right child of 100.
• 700 is the left child of 600.

---

Constraints

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

---

Approach

1. Parse the Traversal String:
   • Read the string sequentially.
   • Count the number of consecutive dashes to determine the depth of the current node.
   • Parse the following digits to form the node's value.
2. Construct the Tree:
   • Use a stack to maintain nodes along the current path.
   • For each node encountered, compare its depth with the depth of the node on the top of the stack.
   • If the current node’s depth is greater, it is the left child of the previous node; otherwise, backtrack in the stack to find the correct parent and attach it as a right child.
3. Return the Root:
   • After processing the entire string, the first element in the stack (or stored separately) will be the root of the reconstructed binary tree.

---

— Written by Saurabh Patil • B.Tech CSE • Software Developer