# LeetCode 1028: Recover a Tree From Preorder Traversal

## Problem Restatement

We run a preorder depth-first traversal on a binary tree.

At each node, we output its depth (as a count of dashes) followed by its value.

For example, a tree with root `1` and left child `2` and right child `5` would produce `"1-2--3--4-5--6--7"` for a specific tree.

We are given this string `traversal` and need to recover the original binary tree.

The official constraints state that the number of nodes is in `[1, 1000]`, `1 <= Node.val <= 10^9`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Preorder traversal string with dash-encoded depths |
| Output | Root of the recovered binary tree |
| Format | `depth_dashes + value`, e.g., `"--5"` means depth 2, value 5 |

Function shape:

```python
def recoverFromPreorder(traversal: str) -> Optional[TreeNode]:
    ...
```

## Examples

Example 1:

```python
traversal = "1-2--3--4-5--6--7"
```

Recovered tree:

```
      1
     / \
    2   5
   / \ / \
  3  4 6  7
```

## Key Insight

Use a stack where position `depth` holds the most recently created node at that depth.

Parse the string to extract `(depth, value)` pairs.

For each pair, create a new node. If the stack has a node at `depth - 1`, attach the new node as a left child (if no left child yet) or right child.

Since preorder visits left before right, the left child is always filled first.

After placing the new node, truncate the stack to depth `depth + 1` so future siblings overwrite it.

## Algorithm

1. Parse the traversal string into `(depth, value)` pairs.
2. Maintain a stack where `stack[d]` is the most recent node at depth `d`.
3. For each `(depth, value)`:
   - Create `node = TreeNode(value)`.
   - If `depth > 0`, attach to `stack[depth - 1]` as left child (if empty) or right child.
   - Set `stack[depth] = node` (or extend the stack).
4. Return `stack[0]`.

## Correctness

In preorder, a node is visited before its children. The depth tells us which level the node belongs to. The first child of a node is always its left child (preorder visits left subtree first).

By maintaining one node per depth level in the stack, we correctly track which parent to attach each new node to.

## Edge Cases

- A missing child should not contribute a fake value to min/max or path computations.
- Leaf nodes often define the base case; verify the behavior on a single-node tree.
- When passing state down the tree, update it before visiting children that depend on the current node.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Parse string once, visit each node once |
| Space | `O(h)` | Stack of height `h` |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from typing import Optional

class Solution:
    def recoverFromPreorder(self, traversal: str) -> Optional[TreeNode]:
        stack = []
        i = 0
        n = len(traversal)

        while i < n:
            depth = 0
            while i < n and traversal[i] == '-':
                depth += 1
                i += 1

            val = 0
            while i < n and traversal[i].isdigit():
                val = val * 10 + int(traversal[i])
                i += 1

            node = TreeNode(val)

            if depth < len(stack):
                stack = stack[:depth]

            if stack:
                parent = stack[-1]
                if parent.left is None:
                    parent.left = node
                else:
                    parent.right = node

            stack.append(node)

        return stack[0]
```

## Code Explanation

Parse depth by counting leading dashes:

```python
while i < n and traversal[i] == '-':
    depth += 1
    i += 1
```

Parse the integer value:

```python
while i < n and traversal[i].isdigit():
    val = val * 10 + int(traversal[i])
    i += 1
```

Truncate the stack to the current depth (removing deeper nodes from previous branches):

```python
if depth < len(stack):
    stack = stack[:depth]
```

Attach to the parent (the top of the trimmed stack):

```python
if parent.left is None:
    parent.left = node
else:
    parent.right = node
```

## Testing

```python
def preorder_vals(root):
    if not root:
        return []
    return [root.val] + preorder_vals(root.left) + preorder_vals(root.right)

def run_tests():
    s = Solution()
    assert preorder_vals(s.recoverFromPreorder("1-2--3--4-5--6--7")) == [1, 2, 3, 4, 5, 6, 7]
    assert preorder_vals(s.recoverFromPreorder("1-2--3---4-5--6---7")) == [1, 2, 3, 4, 5, 6, 7]
    assert preorder_vals(s.recoverFromPreorder("1-401--349---90--88")) == [1, 401, 349, 90, 88]
    print("all tests passed")

run_tests()
```

| Test | Expected Preorder | Why |
|---|---|---|
| Balanced tree | `[1,2,3,4,5,6,7]` | All nodes at correct depths |
| Skewed tree | `[1,2,3,4,5,6,7]` | Different structure, same traversal order |