# LeetCode 889: Construct Binary Tree from Preorder and Postorder Traversal

## Problem Restatement

We are given two arrays:

| Array | Meaning |
|---|---|
| `preorder` | Preorder traversal of a binary tree |
| `postorder` | Postorder traversal of the same binary tree |

The binary tree contains distinct values.

We need to reconstruct and return one possible binary tree. If multiple valid trees exist, returning any one of them is accepted. The problem guarantees that both traversals come from the same binary tree.

Preorder traversal visits nodes in this order:

```text
root, left subtree, right subtree
```

Postorder traversal visits nodes in this order:

```text
left subtree, right subtree, root
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `preorder`, a list of distinct node values |
| Input | `postorder`, a list of distinct node values |
| Output | Root node of one valid binary tree |
| Values | All values are unique |
| Multiple answers | Any valid answer is accepted |

Function shape:

```python
def constructFromPrePost(
    self,
    preorder: list[int],
    postorder: list[int]
) -> Optional[TreeNode]:
    ...
```

## Examples

Example 1:

```text
Input:
preorder  = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]

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

The tree is:

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

Its preorder traversal is:

```text
1, 2, 4, 5, 3, 6, 7
```

Its postorder traversal is:

```text
4, 5, 2, 6, 7, 3, 1
```

Example 2:

```text
Input:
preorder  = [1]
postorder = [1]

Output:
[1]
```

There is only one node, so the answer is a tree with root `1`.

## First Thought: Use the Traversal Roots

The first element in preorder is always the root.

The last element in postorder is always the root.

So for any subtree:

```text
preorder segment:  [root, ...]
postorder segment: [..., root]
```

The root value is easy to find.

The hard part is splitting the remaining nodes into the left subtree and right subtree.

## Key Insight

After the root in preorder, the next value is the root of one child subtree.

Usually, we treat it as the left subtree root:

```text
preorder[pre_left + 1]
```

Then we find this value in postorder.

Why does that help?

Postorder lists the entire left subtree before the right subtree. If `preorder[pre_left + 1]` is the left subtree root, then its position in postorder marks the end of the left subtree.

So if that value appears at index `i` in postorder, then the left subtree size is:

```text
left_size = i - post_left + 1
```

Once we know `left_size`, we can split both traversal arrays into left and right subtree ranges.

Because multiple answers may exist, this convention is valid even when the original tree has only one child at some node.

## Algorithm

Build a hash map:

```python
post_index[value] = index in postorder
```

This lets us find subtree boundaries in `O(1)` time.

Define a recursive function:

```python
build(pre_left, pre_right, post_left, post_right)
```

It constructs the tree represented by:

```text
preorder[pre_left : pre_right + 1]
postorder[post_left : post_right + 1]
```

Steps:

1. If the range is empty, return `None`.
2. Create the root from `preorder[pre_left]`.
3. If the range has one node, return the root.
4. Let `left_root = preorder[pre_left + 1]`.
5. Find `left_root` in postorder.
6. Compute the left subtree size.
7. Recursively build the left subtree.
8. Recursively build the right subtree.
9. Return the root.

## Walkthrough

Use:

```text
preorder  = [1,2,4,5,3,6,7]
postorder = [4,5,2,6,7,3,1]
```

The root is:

```text
1
```

The next preorder value is:

```text
2
```

So we treat `2` as the left subtree root.

In postorder:

```text
[4,5,2,6,7,3,1]
```

value `2` is at index `2`.

So the left subtree has:

```text
2 - 0 + 1 = 3
```

nodes.

Split:

| Part | Preorder | Postorder |
|---|---|---|
| Left subtree | `[2,4,5]` | `[4,5,2]` |
| Right subtree | `[3,6,7]` | `[6,7,3]` |

Now recursively build each side.

For left subtree:

```text
preorder  = [2,4,5]
postorder = [4,5,2]
```

Root is `2`.

Next preorder value is `4`.

In postorder, `4` ends the left subtree, so left child is `4` and right child is `5`.

For right subtree:

```text
preorder  = [3,6,7]
postorder = [6,7,3]
```

Root is `3`.

Left child is `6`, right child is `7`.

The final tree is:

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

## Correctness

For any non-empty subtree, preorder visits the root first. Therefore, `preorder[pre_left]` is the correct root for the current subtree.

If the subtree has one node, the algorithm returns that node, which is correct.

For a larger subtree, the value `preorder[pre_left + 1]` is the root of the first child subtree visited by preorder. The algorithm treats that first child subtree as the left subtree. Since the problem allows any valid answer when multiple trees exist, this choice is acceptable.

In postorder, all nodes of a subtree appear contiguously, and the root of that subtree appears last within that block. Therefore, finding `preorder[pre_left + 1]` in the current postorder range gives the end of that child subtree. This determines exactly how many nodes belong to that subtree.

Using this size, the algorithm splits both preorder and postorder ranges into matching subtree ranges. The recursive calls build valid left and right subtrees from those ranges.

By induction on subtree size, every recursive call returns a tree whose traversals match the given preorder and postorder segments. Therefore, the initial call returns a tree whose preorder and postorder traversals match the input arrays.

## Complexity

Let:

```text
n = len(preorder)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is created once, and each postorder lookup is `O(1)` |
| Space | `O(n)` | The index map and recursion stack use linear space |

## Implementation

```python
# 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 constructFromPrePost(
        self,
        preorder: list[int],
        postorder: list[int]
    ) -> Optional[TreeNode]:
        post_index = {}

        for i, value in enumerate(postorder):
            post_index[value] = i

        def build(pre_left, pre_right, post_left, post_right):
            if pre_left > pre_right:
                return None

            root = TreeNode(preorder[pre_left])

            if pre_left == pre_right:
                return root

            left_root = preorder[pre_left + 1]
            left_root_index = post_index[left_root]
            left_size = left_root_index - post_left + 1

            root.left = build(
                pre_left + 1,
                pre_left + left_size,
                post_left,
                left_root_index
            )

            root.right = build(
                pre_left + left_size + 1,
                pre_right,
                left_root_index + 1,
                post_right - 1
            )

            return root

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

## Code Explanation

We first build an index map for `postorder`:

```python
post_index = {}

for i, value in enumerate(postorder):
    post_index[value] = i
```

This lets us find a node's position in postorder quickly.

The recursive function receives four boundaries:

```python
def build(pre_left, pre_right, post_left, post_right):
```

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

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

If there is only one node, we return it:

```python
if pre_left == pre_right:
    return root
```

Otherwise, the next preorder value begins the first child subtree:

```python
left_root = preorder[pre_left + 1]
```

We find where that subtree ends in postorder:

```python
left_root_index = post_index[left_root]
```

Then compute its size:

```python
left_size = left_root_index - post_left + 1
```

Using that size, we build the left subtree:

```python
root.left = build(
    pre_left + 1,
    pre_left + left_size,
    post_left,
    left_root_index
)
```

and the right subtree:

```python
root.right = build(
    pre_left + left_size + 1,
    pre_right,
    left_root_index + 1,
    post_right - 1
)
```

The `post_right - 1` excludes the current root, because the current root is the last value in the current postorder range.

## Testing

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

def preorder_traversal(root):
    if not root:
        return []

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

def postorder_traversal(root):
    if not root:
        return []

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

def run_tests():
    s = Solution()

    preorder = [1, 2, 4, 5, 3, 6, 7]
    postorder = [4, 5, 2, 6, 7, 3, 1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    preorder = [1]
    postorder = [1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    preorder = [1, 2]
    postorder = [2, 1]
    root = s.constructFromPrePost(preorder, postorder)
    assert preorder_traversal(root) == preorder
    assert postorder_traversal(root) == postorder

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Full binary tree | Standard multi-level reconstruction |
| Single node | Minimum input |
| Two nodes | Multiple valid shapes are possible, traversal match matters |