# Recover a Tree From Preorder Traversal
**Difficulty:** HARD
[External](https://leetcode.com/problems/recover-a-tree-from-preorder-traversal)
Canonical: https://scaleengineer.com/dsa/problems/recover-a-tree-from-preorder-traversal
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** String, Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/recover-a-tree-from-preorder-traversal/image0.png) 

**Input:** traversal = "1-2--3--4-5--6--7"
**Output:** [1,2,5,3,4,6,7]

**Example 2:**

![](https://assets.glich.co/dsa/recover-a-tree-from-preorder-traversal/image1.png) 

**Input:** traversal = "1-2--3---4-5--6---7"
**Output:** [1,2,5,3,null,6,null,4,null,7]

**Example 3:**

![](https://assets.glich.co/dsa/recover-a-tree-from-preorder-traversal/image2.png) 

**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 <= 109`

# Approaches
## Recursive Depth-First Construction
This approach involves two main phases. First, the entire input string is parsed into a list of objects, where each object holds a node's value and its depth in the tree. Second, a recursive function is employed to build the tree from this list. The recursive function mimics a preorder traversal, constructing the tree by matching node depths.
**Time:** O(L), where L is the length of the traversal string. Parsing the string takes O(L) time. The recursive construction visits each of the M nodes once, taking O(M) time. Since M is proportional to L, the total time is O(L). · **Space:** O(M + H), where M is the number of nodes and H is the height of the tree. O(M) space is used for the list of parsed nodes, and O(H) space is used by the recursion call stack. In the worst case (a skewed tree), H ≈ M, so the space complexity is O(M).
**Pros:** The logic is a straightforward recursive implementation of a preorder traversal.; Separating parsing and tree construction can improve code readability.
**Cons:** Requires O(M) extra space for the pre-parsed list of nodes, where M is the number of nodes.; Recursive calls add overhead and could lead to stack overflow on extremely deep trees (though unlikely with given constraints).
### Explanation
The algorithm begins by transforming the raw string into a more structured format, typically a list of pairs `(depth, value)`. A recursive helper function, say `buildTree(nodes, depth)`, is the core of this approach. It attempts to build a subtree whose root should be at the specified `depth`. A global index tracks our position in the list of nodes. When `buildTree` is called, it checks if the node at the current index has the expected `depth`. If it does, a `TreeNode` is created, the index is advanced, and the function recursively calls itself to build the left and right children at `depth + 1`. If the node at the current index has a different depth, it signifies the end of the current branch, and the function returns `null`. The initial call is `buildTree(nodes, 0)` to construct the entire tree, starting from the root at depth 0.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int index = 0;

    // Helper class to store parsed node information
    private static class NodeInfo {
        int depth;
        int val;

        NodeInfo(int depth, int val) {
            this.depth = depth;
            this.val = val;
        }
    }

    public TreeNode recoverFromPreorder(String traversal) {
        List<NodeInfo> nodes = new ArrayList<>();
        int i = 0;
        while (i < traversal.length()) {
            int depth = 0;
            while (i < traversal.length() && traversal.charAt(i) == '-') {
                depth++;
                i++;
            }
            int val = 0;
            while (i < traversal.length() && Character.isDigit(traversal.charAt(i))) {
                val = val * 10 + (traversal.charAt(i) - '0');
                i++;
            }
            nodes.add(new NodeInfo(depth, val));
        }
        return buildTree(nodes, 0);
    }

    private TreeNode buildTree(List<NodeInfo> nodes, int depth) {
        if (index >= nodes.size() || nodes.get(index).depth != depth) {
            return null;
        }

        NodeInfo currentNodeInfo = nodes.get(index++);
        TreeNode node = new TreeNode(currentNodeInfo.val);

        node.left = buildTree(nodes, depth + 1);
        node.right = buildTree(nodes, depth + 1);

        return node;
    }
}
```
### Algorithm
- 1. Parse the input string `traversal` into a list of `(depth, value)` pairs.
- 2. Initialize a global index `i` to 0.
- 3. Define a recursive function `buildTree(nodes, depth)`.
- 4. In `buildTree`, if `i` is out of bounds or `nodes[i].depth` is not equal to `depth`, return `null`.
- 5. Otherwise, create a `TreeNode` with `nodes[i].value`, and increment `i`.
- 6. Set the node's left child by calling `buildTree(nodes, depth + 1)`.
- 7. Set the node's right child by calling `buildTree(nodes, depth + 1)`.
- 8. Return the created node.
- 9. Start the process by calling `buildTree(nodes, 0)`.

## Iterative Construction with a Stack
This is a more optimized approach that processes the string iteratively, building the tree on the fly. It uses a stack to keep track of the current path from the root. This avoids the need for a full pre-parsing step and the overhead of recursion.
**Time:** O(L), where L is the length of the traversal string. The string is traversed once. Each node is pushed onto and popped from the stack at most once, leading to an amortized O(1) time for stack operations per node. Thus, the total time is linear. · **Space:** O(H), where H is the height of the tree. The space is dominated by the stack, which stores the current path of nodes. In the worst case of a skewed tree, H can be up to M (the number of nodes), making the complexity O(M).
**Pros:** Highly efficient in terms of space, using only O(H) space for the stack, where H is the tree height.; Avoids recursion, which eliminates function call overhead and the risk of stack overflow.; Processes the tree in a single pass without needing an intermediate data structure for all nodes.
**Cons:** The logic for managing the stack to find the parent might be slightly more complex to grasp initially compared to the direct recursive approach.
### Explanation
The algorithm iterates through the string, parsing one node (`depth` and `value`) at a time. A stack of `TreeNode`s is maintained to represent the path from the root to the parent of the node currently being added. For each new node, we determine its parent by looking at its `depth`. We pop nodes from the stack until the size of the stack equals the `depth` of the new node. The node at the top of the stack is then the correct parent. Once the parent is found, the new node is attached. Since it's a preorder traversal, we first try to attach it as the left child. If the left child is already occupied, we attach it as the right child. The new node is then pushed onto the stack, extending the current path. The process continues until the entire string is parsed. The root of the tree is the first node that was pushed onto the stack.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode recoverFromPreorder(String traversal) {
        Stack<TreeNode> path = new Stack<>();
        int i = 0;
        while (i < traversal.length()) {
            int depth = 0;
            while (i < traversal.length() && traversal.charAt(i) == '-') {
                depth++;
                i++;
            }

            int val = 0;
            while (i < traversal.length() && Character.isDigit(traversal.charAt(i))) {
                val = val * 10 + (traversal.charAt(i) - '0');
                i++;
            }
            
            TreeNode node = new TreeNode(val);

            while (path.size() > depth) {
                path.pop();
            }

            if (!path.isEmpty()) {
                TreeNode parent = path.peek();
                if (parent.left == null) {
                    parent.left = node;
                } else {
                    parent.right = node;
                }
            }
            
            path.push(node);
        }
        
        // The root is at the bottom of the stack
        while (path.size() > 1) {
            path.pop();
        }
        return path.isEmpty() ? null : path.peek();
    }
}
```
### Algorithm
- 1. Initialize an empty stack `path` to store `TreeNode`s.
- 2. Iterate through the `traversal` string with an index `i`.
- 3. In each iteration, parse the `depth` (by counting dashes) and `value` (by reading digits) of the next node.
- 4. Create a new `TreeNode`.
- 5. Adjust the `path` stack: pop nodes from the stack until `path.size()` is equal to the `depth` of the new node.
- 6. If the stack is not empty, the top element is the parent. Attach the new node as its left or right child.
- 7. Push the new node onto the stack.
- 8. After the loop, the root is the only element remaining at the bottom of the stack. Pop until one element is left and return it.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode recoverFromPreorder ( String traversal ) { Stack < TreeNode > stack = new Stack <>(); int i = 0 ; while ( i < traversal . length ()) { int depth = 0 ; while ( i < traversal . length () && traversal . charAt ( i ) == '-' ) { depth ++; i ++; } int num = 0 ; while ( i < traversal . length () && Character . isDigit ( traversal . charAt ( i ))) { num = num * 10 + ( traversal . charAt ( i ) - '0' ); i ++; } // Create the new node TreeNode newNode = new TreeNode ( num ); while ( stack . size () > depth ) { stack . pop (); } if (! stack . isEmpty ()) { if ( stack . peek (). left == null ) { stack . peek (). left = newNode ; } else { stack . peek (). right = newNode ; } } stack . push ( newNode ); } return stack . isEmpty () ? null : stack . get ( 0 ); } }
```

### JavaScript

```javascript
function recoverFromPreorder ( traversal ) { const stack = []; let i = 0 ; while ( i < traversal . length ) { let depth = 0 ; while ( i < traversal . length && traversal [ i ] === ' - ' ) { depth ++ ; i ++ ; } let num = 0 ; while ( i < traversal . length && ! Number . isNaN ( + traversal [ i ])) { num = num * 10 + + traversal [ i ]; i ++ ; } // Create the new node const newNode = new TreeNode ( num ); while ( stack . length > depth ) { stack . pop (); } if ( stack . length > 0 ) { const i = stack . length - 1 ; if ( stack [ i ]. left === null ) { stack [ i ]. left = newNode ; } else { stack [ i ]. right = newNode ; } } stack . push ( newNode ); } return stack . length ? stack [ 0 ] : null ; }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode * recoverFromPreorder ( string S ) { stack < TreeNode *> st ; int depth = 0 ; int num = 0 ; for ( int i = 0 ; i < S . length (); ++ i ) { if ( S [ i ] == '-' ) { depth ++ ; } else { num = 10 * num + S [ i ] - '0' ; } if ( i + 1 >= S . length () || ( isdigit ( S [ i ]) && S [ i + 1 ] == '-' )) { TreeNode * newNode = new TreeNode ( num ); while ( st . size () > depth ) { st . pop (); } if ( ! st . empty ()) { if ( st . top () -> left == nullptr ) { st . top () -> left = newNode ; } else { st . top () -> right = newNode ; } } st . push ( newNode ); depth = 0 ; num = 0 ; } } TreeNode * res ; while ( ! st . empty ()) { res = st . top (); st . pop (); } return res ; } };
```