# LeetCode 106: Construct Binary Tree from Inorder and Postorder Traversal

## Problem Restatement

We are given two integer arrays:

```python
inorder
postorder
```

Both arrays describe the same binary tree.

`inorder` is the inorder traversal of the tree.

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

We need to construct and return the original binary tree. The values are unique, and both arrays are guaranteed to describe the same tree. The official constraints also say each value in `postorder` appears in `inorder`.

The traversal rules are:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two integer arrays, `inorder` and `postorder` |
| Output | The root of the constructed binary tree |
| Inorder meaning | Left subtree, then root, then right subtree |
| Postorder meaning | Left subtree, then right subtree, then root |
| 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, inorder: list[int], postorder: list[int]) -> Optional[TreeNode]:
        ...
```

## Examples

Consider:

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

The last value in postorder 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
inorder right part   = [15, 20, 7]
postorder right part = [15, 7, 20]
```

The last value in that postorder range 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

Postorder gives us the root at the end:

```text
postorder[last] 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.

This is very similar to LeetCode 105, but the root comes from the end of the postorder range instead of the beginning of the preorder range.

## Key Insight

For every subtree, the last value in its postorder range is the subtree root.

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

That position tells us how many nodes belong to the left subtree and how many belong to the right 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
```

The right subtree size is:

```python
right_size = in_right - root_index
```

To avoid scanning `inorder` again and again, build a hash map:

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

Then each root lookup is constant time.

## Algorithm

Build a dictionary called `in_pos`:

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

Then define a recursive function:

```python
build(in_left, in_right, post_left, post_right)
```

This function builds the tree from:

```text
inorder[in_left : in_right + 1]
postorder[post_left : post_right + 1]
```

For each call:

1. If the inorder range is empty, return `None`.
2. The root value is `postorder[post_right]`.
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
inorder:   in_left to root_index - 1
postorder: post_left to post_left + left_size - 1
```

The right subtree ranges are:

```text
inorder:   root_index + 1 to in_right
postorder: post_left + left_size to post_right - 1
```

The `post_right - 1` endpoint skips the root, because `postorder[post_right]` has already been used.

## Correctness

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

In inorder traversal, all values before the root belong to the left subtree, and all values after the root belong to the right subtree. Since 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 left subtree size from the inorder split. It then uses that size to take exactly the correct number of values from the postorder range for the left subtree. The remaining values before the root in the postorder range belong to the right subtree.

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

Therefore, every node is created once, attached under the correct parent, and placed in the correct left or right subtree. The returned root is the binary tree described by the two traversal arrays.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is created once, and each inorder index lookup is `O(1)` |
| 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, inorder: list[int], postorder: list[int]) -> Optional[TreeNode]:
        in_pos = {}

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

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

            root_value = postorder[post_right]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

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

            root.right = build(
                root_index + 1,
                in_right,
                post_left + left_size,
                post_right - 1,
            )

            return root

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

## Code Explanation

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

```python
in_pos = {}

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

This makes root lookup fast.

The helper function receives index boundaries:

```python
def build(in_left, in_right, post_left, post_right):
```

These boundaries describe one subtree.

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

```python
if in_left > in_right:
    return None
```

The last value in the current postorder range is the root:

```python
root_value = postorder[post_right]
root = TreeNode(root_value)
```

Find the root in inorder:

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

Compute the number of nodes in the left subtree:

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

Build the left subtree:

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

Build the right subtree:

```python
root.right = build(
    root_index + 1,
    in_right,
    post_left + left_size,
    post_right - 1,
)
```

Finally, return the root:

```python
return root
```

## Testing

To test construction, serialize the tree back into inorder and postorder and compare with the original arrays.

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

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

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

            root_value = postorder[post_right]
            root = TreeNode(root_value)

            root_index = in_pos[root_value]
            left_size = root_index - in_left

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

            root.right = build(
                root_index + 1,
                in_right,
                post_left + left_size,
                post_right - 1,
            )

            return root

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

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

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

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

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

def run_tests():
    s = Solution()

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

    inorder2 = [-1]
    postorder2 = [-1]
    root2 = s.buildTree(inorder2, postorder2)
    assert inorder_values(root2) == inorder2
    assert postorder_values(root2) == postorder2

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

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