Skip to main content

Construct Binary Tree from Preorder and Inorder Traversal

LeetCode 105 | Difficulty: Medium​

Medium

Problem Description​

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:

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

Example 2:

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.

Topics: Array, Hash Table, Divide and Conquer, Tree, Binary Tree

Approach​

Hash Map​

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Solutions​

Complexity Analysis​

ApproachTimeSpace
Hash Map$O(n)$$O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.
  • Consider: "What information do I need from each subtree?" — this defines your recursive return value.
  • Hash map gives O(1) lookup — think about what to use as key vs value.