Construct Binary Tree from Preorder and Inorder Traversal
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.
The first preorder element is always the current root. Find that value's position in the inorder array — everything to its left forms the left subtree, everything to its right forms the right subtree. Recurse with the matching slices of preorder.
preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]level-order: [3, 9, 20, _, _, 15, 7]def build_tree(preorder, inorder):
pos = {v: i for i, v in enumerate(inorder)}
pi = [0]
def rec(lo, hi):
if lo > hi: return None
v = preorder[pi[0]]; pi[0] += 1
node = TreeNode(v)
m = pos[v]
node.left = rec(lo, m - 1)
node.right = rec(m + 1, hi)
return node
return rec(0, len(inorder) - 1)function buildTree(preorder, inorder) {
const pos = new Map();
inorder.forEach((v, i) => pos.set(v, i));
let pi = 0;
function rec(lo, hi) {
if (lo > hi) return null;
const v = preorder[pi++];
const node = { val: v, left: null, right: null };
const m = pos.get(v);
node.left = rec(lo, m - 1);
node.right = rec(m + 1, hi);
return node;
}
return rec(0, inorder.length - 1);
}class Solution {
int pi = 0;
Map<Integer, Integer> pos = new HashMap<>();
int[] pre;
public TreeNode buildTree(int[] preorder, int[] inorder) {
pre = preorder;
for (int i = 0; i < inorder.length; i++) pos.put(inorder[i], i);
return rec(0, inorder.length - 1);
}
TreeNode rec(int lo, int hi) {
if (lo > hi) return null;
int v = pre[pi++];
TreeNode node = new TreeNode(v);
int m = pos.get(v);
node.left = rec(lo, m - 1);
node.right = rec(m + 1, hi);
return node;
}
}int pi = 0;
unordered_map<int,int> pos;
vector<int> pre_;
TreeNode* rec(int lo, int hi) {
if (lo > hi) return nullptr;
int v = pre_[pi++];
auto node = new TreeNode(v);
int m = pos[v];
node->left = rec(lo, m - 1);
node->right = rec(m + 1, hi);
return node;
}Explanation
We rebuild a binary tree from its preorder and inorder lists. The key fact is that the first value in preorder is always the root, and inorder then tells us how to split the rest into the left and right subtrees.
We pre-build a lookup map pos from value to its index in inorder so the split point is found in O(1). A pointer pi walks preorder from the front, handing us roots in the exact order we need them.
Preorder is laid out as root, left, right, so after taking a root we recurse into node.left first, then node.right. The range [lo, hi] is the slice of inorder this subtree owns; lo > hi means empty.
Example: preorder = [3, 9, 20, 15, 7], inorder = [9, 3, 15, 20, 7]. First value 3 is the root; it sits at inorder index 1, so left is [9] and right is [15, 20, 7]. The next preorder value 9 builds the left leaf, then 20 roots the right subtree, splitting into 15 and 7.
Each value is consumed once and every split is instant, so the tree is rebuilt in linear time.