> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Construct Binary Tree from Preorder and

> Tested Python solution for LeetCode 105 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 105, Medium. Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree. [View on LeetCode](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/).

Generate this problem as a practice environment: tested reference solution, 16 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 105   # by problem number
lcpy gen -s construct_binary_tree_from_preorder_and_inorder_traversal   # by problem name
```

## Problem

Given two integer arrays `preorder` and `inorder` where `preorder` is the preorder traversal of a binary tree and `inorder` is the inorder traversal of the same tree, construct and return the binary tree.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/02/19/tree.jpg)

```
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
```

```
Input: preorder = [-1], inorder = [-1]
Output: [-1]
```

### Constraints

* 1 \<= preorder.length \<= 3000
* inorder.length == preorder.length
* -3000 \<= preorder\[i], inorder\[i] \<= 3000
* preorder and inorder consist of unique values.
* Each value of inorder also appears in preorder.
* preorder is guaranteed to be the preorder traversal of the tree.
* inorder is guaranteed to be the inorder traversal of the tree.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/construct_binary_tree_from_preorder_and_inorder_traversal/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/construct_binary_tree_from_preorder_and_inorder_traversal/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from leetcode_py import TreeNode


class Solution:
    """
    Construct Binary Tree from Preorder and Inorder Traversal

    Algorithm Explanation:
    - Preorder: Root -> Left -> Right (first element is always root)
    - Inorder: Left -> Root -> Right (root splits left/right subtrees)

    Example: preorder=[3,9,20,15,7], inorder=[9,3,15,20,7]

    Step 1: Root = 3 (first in preorder)
            Find 3 in inorder at index 1
            Left subtree: inorder[0:1] = [9]
            Right subtree: inorder[2:] = [15,20,7]

    Step 2: Build left subtree with preorder=[9], inorder=[9]
            Root = 9, no children

    Step 3: Build right subtree with preorder=[20,15,7], inorder=[15,20,7]
            Root = 20, left=[15], right=[7]

    Final tree:
           3
          / \
         9   20
            /  \
           15   7
    """

    # Time: O(n) - hashmap lookup O(1) for each of n nodes
    # Space: O(n) - hashmap + recursion stack
    def build_tree(self, preorder: list[int], inorder: list[int]) -> TreeNode | None:
        if not preorder or not inorder:
            return None

        inorder_map = {val: i for i, val in enumerate(inorder)}
        self.preorder_index = 0

        def build(left: int, right: int) -> TreeNode | None:
            # left, right: boundaries in inorder array for current subtree
            if left > right:
                return None

            root_val = preorder[self.preorder_index]
            self.preorder_index += 1
            root = TreeNode(root_val)

            mid = inorder_map[root_val]  # root position in inorder
            # Left subtree: inorder[left:mid-1]
            root.left = build(left, mid - 1)
            # Right subtree: inorder[mid+1:right]
            root.right = build(mid + 1, right)

            return root

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

## Complexity

| Time                                           | Space                            |
| ---------------------------------------------- | -------------------------------- |
| O(n) - hashmap lookup O(1) for each of n nodes | O(n) - hashmap + recursion stack |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).