Given two integer arrays preorder and inorder, where preorder is the preorder traversal and inorder is the inorder traversal of the same binary tree, construct and return the tree. You may assume that all values are unique and both arrays have the same length (between 1 and 3000). Each value is in the range [-3000, 3000].
Example
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]
Output:
3
/ \
9 20
/ \
15 7
Both traversals describe the same tree. The preorder tells us 3 is the root, and the inorder tells us 9 is in the left subtree while 20, 15, 7 are in the right subtree.
The first element of preorder is always the root. Find that root's position in inorder — everything to its left is the left subtree, everything to its right is the right subtree. Use a hashmap for O(1) index lookups in inorder, then recursively build each subtree.
Why this works
Preorder traversal visits the root first, then left subtree, then right subtree. Inorder traversal visits left subtree, then root, then right subtree. So the first element in preorder tells you the root, and finding that root in inorder tells you how to split elements into “left subtree” and “right subtree” groups. Recursing on each group builds the full tree.
Step by step
- Build a hashmap — map each value in inorder to its index for O(1) lookups.
- Pick the root — take the next element from preorder (using a pointer that advances globally).
- Find the split — look up the root’s position in inorder. Everything to its left belongs to the left subtree, everything to its right belongs to the right subtree.
- Recurse left, then right — build the left subtree first (matching preorder’s order), then the right subtree.
Time: O(n)
Space: O(n)
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
class Solution {
private int preIdx = 0;
private Map<Integer, Integer> inorderIndex;
public TreeNode buildTree(int[] preorder, int[] inorder) {
inorderIndex = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderIndex.put(inorder[i], i); // O(1) lookup for root position
}
return build(preorder, 0, inorder.length - 1);
}
private TreeNode build(int[] preorder, int left, int right) {
if (left > right) {
return null;
}
int rootVal = preorder[preIdx++]; // next root is always next in preorder
TreeNode root = new TreeNode(rootVal);
int mid = inorderIndex.get(rootVal); // split inorder into left and right subtrees
root.left = build(preorder, left, mid - 1);
root.right = build(preorder, mid + 1, right);
return root;
}
}
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> inorderIndex;
for (int i = 0; i < inorder.size(); i++) {
inorderIndex[inorder[i]] = i; // O(1) lookup for root position
}
int preIdx = 0;
return build(preorder, inorderIndex, preIdx, 0, inorder.size() - 1);
}
private:
TreeNode* build(vector<int>& preorder, unordered_map<int, int>& inorderIndex,
int& preIdx, int left, int right) {
if (left > right) {
return nullptr;
}
int rootVal = preorder[preIdx++]; // next root is always next in preorder
TreeNode* root = new TreeNode(rootVal);
int mid = inorderIndex[rootVal]; // split inorder into left and right subtrees
root->left = build(preorder, inorderIndex, preIdx, left, mid - 1);
root->right = build(preorder, inorderIndex, preIdx, mid + 1, right);
return root;
}
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def buildTree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
inorder_index = {val: i for i, val in enumerate(inorder)} # O(1) lookup for root position
pre_idx = [0]
def build(left, right):
if left > right:
return None
root_val = preorder[pre_idx[0]] # next root is always next in preorder
pre_idx[0] += 1
root = TreeNode(root_val)
mid = inorder_index[root_val] # split inorder into left and right subtrees
root.left = build(left, mid - 1)
root.right = build(mid + 1, right)
return root
return build(0, len(inorder) - 1)