Medium·[2026-03-26]
105. Construct Binary Tree from Preorder and Inorder Traversal
[#binary-tree, #dfs]
## description
## 105. Construct Binary Tree from Preorder and Inorder Traversal
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.
Example 1:
plain text
1Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
2Output: [3,9,20,null,null,15,7]Example 2:
plain text
1Input: preorder = [-1], inorder = [-1]
2Output: [-1]- –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.
Constraints:
## notes
### Intuition
The inorder traversal splits the tree into left and right at each node. In other words, everything to the right of the node in the inorder traversal is on the right side and everything on the left is on the left side.
### Implementation
We can use DFS to construct the tree in a pre-order fashion.
In our DFS function, we take in a range of left and right as parameters.
- –If the left is greater than the right, we return None.
- –We take the next value from the preorder traversal (index tracked globally) and create a node with that value.
- –We find the index of that value in the inorder traversal using a hashmap for O(1) lookups. This is the mid point of the left and right subtrees.
- –We recursively set the left child of the node to be the result of calling DFS on the left and mid - 1.
- –We recursively set the right child of the node to be the result of calling DFS on the mid + 1 and right.
Finally, we call the DFS function with the initial range of 0 and n - 1, where n is the length of the inorder traversal.
- –Time: O(n), we visit each node once.
- –Space: O(n), the hashmap takes O(n) space and the recursion stack takes O(n) space.
### Complexity
## solution
python
1from typing import List, Optional
2from lcutils import TreeNode
3
4# Definition for a binary tree node.
5# class TreeNode:
6# def __init__(self, val=0, left=None, right=None):
7# self.val = val
8# self.left = left
9# self.right = right
10class Solution:
11 def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
12 inorder_map = { val: idx for idx, val in enumerate(inorder) }
13 i = 0
14 def dfs(l: int, r: int) -> Optional[TreeNode]:
15 nonlocal i
16 if l > r:
17 return None
18
19 root_val = preorder[i]
20 root = TreeNode(root_val)
21 mid = inorder_map[root_val]
22 i += 1
23 root.left = dfs(l, mid - 1)
24 root.right = dfs(mid + 1, r)
25 return root
26 return dfs(0, len(inorder) - 1)
27
28
29
30if __name__ == "__main__":
31 # Include one-off tests here or debugging logic that can be run by running this file
32 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
33 solution = Solution()
34--EOF--