# LeetCode 1008: Construct Binary Search Tree from Preorder Traversal

## Problem Restatement

We are given the preorder traversal of a binary search tree (BST) in an array `preorder`.

We need to reconstruct the BST and return its root.

Recall that in a BST, for every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

In preorder traversal, we visit the root before the left and right subtrees.

The official constraints state that `1 <= preorder.length <= 100`, all values in `preorder` are distinct, and it is guaranteed that the input represents a valid BST.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Preorder traversal array `preorder` |
| Output | Root of the reconstructed BST |

Function shape:

```python
def bstFromPreorder(preorder: list[int]) -> Optional[TreeNode]:
    ...
```

## Examples

Example 1:

```python
preorder = [8, 5, 1, 7, 10, 12]
```

Root is `8`. Left subtree has values `[5, 1, 7]` (all less than `8`). Right subtree has values `[10, 12]` (all greater than `8`).

The BST:

```
      8
     / \
    5   10
   / \    \
  1   7   12
```

## Key Insight

In preorder traversal, the first element is always the root.

All subsequent elements less than the root belong to the left subtree.

All subsequent elements greater than the root belong to the right subtree.

We can find the split point and recursively build left and right subtrees.

Alternatively, use a range-based recursive approach with an index pointer:

- The root is `preorder[index]`.
- The left subtree takes values less than the upper bound.
- The right subtree takes values greater than the lower bound.

## Algorithm

Use a recursive function with a global index and value bounds:

1. If the index is out of bounds or the current value is out of the `[lower, upper)` range, return `None`.
2. Create a node with the current value.
3. Advance the index.
4. Recursively build the left child with upper bound set to the current node's value.
5. Recursively build the right child with lower bound set to the current node's value.
6. Return the node.

## Correctness

The BST property guarantees that all values for the left subtree fall in `(lower, root.val)` and all values for the right subtree fall in `(root.val, upper)`.

Preorder traversal visits root, then left subtree, then right subtree. So consuming elements in preorder with the correct bounds produces exactly the right subtree structure.

## 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)` | Each node is visited once |
| Space | `O(h)` | Recursion stack of tree height, up to `O(n)` in the worst case |

## 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 TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> Optional[TreeNode]:
        self.idx = 0

        def build(lower: float, upper: float) -> Optional[TreeNode]:
            if self.idx == len(preorder):
                return None
            val = preorder[self.idx]
            if val < lower or val > upper:
                return None

            node = TreeNode(val)
            self.idx += 1
            node.left = build(lower, val)
            node.right = build(val, upper)
            return node

        return build(float("-inf"), float("inf"))
```

## Code Explanation

We maintain a shared index pointing to the current preorder element:

```python
self.idx = 0
```

The recursive function checks whether the current value fits within the allowed range:

```python
val = preorder[self.idx]
if val < lower or val > upper:
    return None
```

If valid, create the node and advance the index:

```python
node = TreeNode(val)
self.idx += 1
```

Recursively build left and right subtrees with updated bounds:

```python
node.left = build(lower, val)
node.right = build(val, upper)
```

## Alternative: Split by Index

We can also find where the right subtree starts using binary search on the preorder array.

```python
class Solution:
    def bstFromPreorder(self, preorder: list[int]) -> Optional[TreeNode]:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        mid = len(preorder)
        for i in range(1, len(preorder)):
            if preorder[i] > preorder[0]:
                mid = i
                break
        root.left = self.bstFromPreorder(preorder[1:mid])
        root.right = self.bstFromPreorder(preorder[mid:])
        return root
```

This approach is simpler but creates subarrays, making it `O(n^2)` in the worst case.

## Testing

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

def run_tests():
    s = Solution()

    root = s.bstFromPreorder([8, 5, 1, 7, 10, 12])
    assert preorder_list(root) == [8, 5, 1, 7, 10, 12]

    root = s.bstFromPreorder([1, 3])
    assert preorder_list(root) == [1, 3]

    root = s.bstFromPreorder([5])
    assert preorder_list(root) == [5]

    print("all tests passed")

run_tests()
```

| Test | Expected Preorder | Why |
|---|---|---|
| `[8,5,1,7,10,12]` | `[8,5,1,7,10,12]` | Standard BST reconstruction |
| `[1,3]` | `[1,3]` | Two nodes, right child |
| `[5]` | `[5]` | Single node |