# LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal

## Problem Restatement

We are given two integer arrays:

```python
preorder
inorder
```

Both arrays describe the same binary tree.

`preorder` is the preorder traversal of the tree.

`inorder` is the inorder traversal of the same tree.

We need to construct and return the original binary tree. The official problem states that `preorder` and `inorder` are traversals of the same tree.

The key traversal rules are:

```text
preorder: root -> left -> right
inorder:  left -> root -> right
```

The node values are unique, so each value appears in exactly one place in the tree.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integer arrays, `preorder` and `inorder` |
| Output | The root of the constructed binary tree |
| Preorder meaning | Root first, then left subtree, then right subtree |
| Inorder meaning | Left subtree, then root, then right subtree |
| Important condition | Node values are unique |

LeetCode gives the `TreeNode` class:

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
```

The function shape is:

```python
class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        ...
```

## Examples

Consider:

```python
preorder = [3, 9, 20, 15, 7]
inorder  = [9, 3, 15, 20, 7]
```

The first value in preorder is always the root:

```python
3
```

Now find `3` in inorder:

```text
[9] 3 [15, 20, 7]
```

Everything left of `3` belongs to the left subtree:

```python
[9]
```

Everything right of `3` belongs to the right subtree:

```python
[15, 20, 7]
```

So the tree starts like this:

```text
        3
      /   \
     9     ?
```

Now build the right subtree from:

```python
preorder right part = [20, 15, 7]
inorder right part  = [15, 20, 7]
```

The root is `20`.

In inorder:

```text
[15] 20 [7]
```

So `15` is the left child and `7` is the right child.

The final tree is:

```text
        3
      /   \
     9     20
          /  \
         15   7
```

## First Thought: Use the Traversal Definitions

The traversal arrays are not arbitrary lists.

They encode structure.

Preorder tells us the root immediately:

```text
preorder[0] is the root
```

Inorder tells us how to split the tree:

```text
values before root  -> left subtree
values after root   -> right subtree
```

So after finding the root, we can recursively build the left and right subtrees.

## Key Insight

The root of each subtree appears first in that subtree's preorder range.

Once we know the root value, we find its position in inorder.

That position tells us the number of nodes in the left subtree.

For a subtree whose inorder range is:

```text
in_left ... in_right
```

and whose root appears at:

```text
root_index
```

the left subtree size is:

```python
left_size = root_index - in_left
```

This size lets us split the preorder range correctly.

To avoid searching inside `inorder` every time, we build a hash map:

```python
value -> index in inorder
```

Then each root position lookup is `O(1)`.

## Algorithm

Build a dictionary called `in_pos`:

```python
in_pos[value] = index
```

Then define a recursive function:

```python
build(pre_left, pre_right, in_left, in_right)
```

This function builds the tree from:

```text
preorder[pre_left : pre_right + 1]
inorder[in_left : in_right + 1]
```

For each call:

1. If the preorder range is empty, return `None`.
2. The root value is `preorder[pre_left]`.
3. Create a `TreeNode` with that value.
4. Find the root position in inorder using `in_pos`.
5. Compute the left subtree size.
6. Recursively build the left subtree.
7. Recursively build the right subtree.
8. Return the root node.

The left subtree ranges are:

```text
preorder: pre_left + 1 to pre_left + left_size
inorder:  in_left to root_index - 1
```

The right subtree ranges are:

```text
preorder: pre_left + left_size + 1 to pre_right
inorder:  root_index + 1 to in_right
```

## Correctness

The first element of a preorder traversal is the root of the current tree. Therefore, each recursive call chooses the correct root for its current subtree.

In inorder traversal, every value before the root belongs to the left subtree, and every value after the root belongs to the right subtree. Because all values are unique, the root has one exact position in the inorder array. This gives one exact split into left and right subtrees.

The algorithm computes the size of the left subtree from that inorder split. It then uses that size to take exactly the correct number of nodes from preorder for the left subtree. The remaining nodes in the current preorder range belong to the right subtree.

The recursive calls apply the same reasoning to each subtree. When a subtree range becomes empty, the algorithm returns `None`, which correctly represents a missing child.

Therefore, every node is created once, attached to the correct parent, and placed in the correct left or right subtree. The returned root is the original binary tree described by the traversals.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is created once, and each inorder index lookup is constant time |
| Space | `O(n)` | The hash map stores `n` values, and recursion uses stack space |

Here, `n` is the number of nodes.

The recursion stack is `O(h)`, where `h` is the tree height. In the worst case, `h = n`.

## Implementation

```python
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
            if pre_left > pre_right:
                return None

            root_value = preorder[pre_left]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                in_left,
                root_index - 1,
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                root_index + 1,
                in_right,
            )

            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1)
```

## Code Explanation

First, we store each value's index in `inorder`:

```python
in_pos = {}

for i, value in enumerate(inorder):
    in_pos[value] = i
```

This avoids repeated linear scans.

The helper function receives index boundaries:

```python
def build(pre_left, pre_right, in_left, in_right):
```

These boundaries describe the current subtree.

If the preorder range is empty, there is no node to build:

```python
if pre_left > pre_right:
    return None
```

The first value in the current preorder range is the root:

```python
root_value = preorder[pre_left]
root = TreeNode(root_value)
```

Find where this root appears in inorder:

```python
root_index = in_pos[root_value]
```

Then compute how many nodes belong to the left subtree:

```python
left_size = root_index - in_left
```

Now build the left subtree:

```python
root.left = build(
    pre_left + 1,
    pre_left + left_size,
    in_left,
    root_index - 1,
)
```

The left subtree starts right after the root in preorder and has `left_size` nodes.

Then build the right subtree:

```python
root.right = build(
    pre_left + left_size + 1,
    pre_right,
    root_index + 1,
    in_right,
)
```

Finally, return the root:

```python
return root
```

## Testing

To test tree construction, it is easier to serialize the result back into preorder and inorder and compare them with the input.

```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 buildTree(self, preorder: list[int], inorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

        for i, value in enumerate(inorder):
            in_pos[value] = i

        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> Optional[TreeNode]:
            if pre_left > pre_right:
                return None

            root_value = preorder[pre_left]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                in_left,
                root_index - 1,
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                root_index + 1,
                in_right,
            )

            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1)

def preorder_values(root):
    if root is None:
        return []

    return [root.val] + preorder_values(root.left) + preorder_values(root.right)

def inorder_values(root):
    if root is None:
        return []

    return inorder_values(root.left) + [root.val] + inorder_values(root.right)

def run_tests():
    s = Solution()

    preorder1 = [3, 9, 20, 15, 7]
    inorder1 = [9, 3, 15, 20, 7]
    root1 = s.buildTree(preorder1, inorder1)
    assert preorder_values(root1) == preorder1
    assert inorder_values(root1) == inorder1

    preorder2 = [-1]
    inorder2 = [-1]
    root2 = s.buildTree(preorder2, inorder2)
    assert preorder_values(root2) == preorder2
    assert inorder_values(root2) == inorder2

    preorder3 = [1, 2, 3, 4]
    inorder3 = [4, 3, 2, 1]
    root3 = s.buildTree(preorder3, inorder3)
    assert preorder_values(root3) == preorder3
    assert inorder_values(root3) == inorder3

    preorder4 = [1, 2, 3, 4]
    inorder4 = [1, 2, 3, 4]
    root4 = s.buildTree(preorder4, inorder4)
    assert preorder_values(root4) == preorder4
    assert inorder_values(root4) == inorder4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[3,9,20,15,7]`, `[9,3,15,20,7]` | Standard mixed tree |
| Single node | Minimum valid tree |
| Left-skewed tree | Confirms recursive left ranges |
| Right-skewed tree | Confirms recursive right ranges |