> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/trees/recover-a-tree-from-preorder-traversal.md).

# Recover a Tree From Preorder Traversal

We run a preorder depth first search 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 `S` of this traversal, recover the tree and return its `root`.

**Example 1:**

![](https://assets.leetcode.com/uploads/2019/04/08/recover-a-tree-from-preorder-traversal.png)

```
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114101-pm.png)

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

**Example 3:**

![](https://assets.leetcode.com/uploads/2019/04/11/screen-shot-2019-04-10-at-114955-pm.png)

```
Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]
```

**Note:**

* The number of nodes in the original tree is between `1` and `1000`.
* Each node will have a value between `1` and `10^9`.

```java
class Solution {
    public TreeNode helper(String s, int start, int end) {
        if (start > end)
            return null;
        StringBuilder number = new StringBuilder();
        while (start <= end && s.charAt(start) >= '0' && s.charAt(start) <= '9')
            number.append(s.charAt(start++));
        int val = Integer.parseInt(number.toString());
        TreeNode root = new TreeNode(val);
        if (start > end)
            return root;
        int len = 0;
        int rightindex = -1;
        while (start <= end && s.charAt(start) == '-') {
            start++;
            len++;
        }
        for (int i = start; i <= end; i++) {
            int lenDashes = 0;
            boolean dash = false;
            while (i <= end && s.charAt(i) == '-') {
                i++;
                lenDashes++;
                dash = true;
            }
            if (dash && lenDashes == len) {
                rightindex = i - lenDashes;
                i--;
                break;
            }
        }
        if (rightindex == -1)
            root.left = helper(s, start, end);
        else {
            root.left = helper(s, start, rightindex - 1);
            root.right = helper(s, rightindex + len, end);
        }
        return root;
    }

    public TreeNode recoverFromPreorder(String S) {
        return helper(S, 0, S.length() - 1);
    }
}
```