Pattern Reference
Tree Construction
"Build trees from traversals, serialization, construct BST from preorder."
Loading...
Deep Dive Tutorial
Tree reconstruction works because different traversal types provide complementary information. Preorder/postorder identifies the root of every subtree. Inorder splits left and right subtrees. Combining two traversals uniquely determines the tree (for distinct values). The algorithm: find root in inorder, split into left/right sizes, recurse on each half.
| Given | Unique tree? | Algorithm |
|---|---|---|
| Preorder + Inorder | Yes (distinct values) | preorder[0] = root; find in inorder; split |
| Postorder + Inorder | Yes (distinct values) | postorder[last] = root; find in inorder; split |
| Preorder + Postorder | Not always (no inorder) | Works for full binary trees only |
| Inorder only | No | Multiple trees have same inorder |
| BST + Preorder | Yes | Use BST property to split without inorder |
| BST + Postorder | Yes | Same — BST property determines left/right |
Core Algorithm: Preorder + Inorder
Build tree from preorder and inorder traversals
// preorder[0] = root
// inorder[rootIdx] splits: left = inorder[0..rootIdx-1], right = inorder[rootIdx+1..]
// preorder[1..rootIdx] = left subtree preorder (size = rootIdx)
// preorder[rootIdx+1..] = right subtree preorder
function buildTree(preorder, inorder) {
const inorderMap = new Map(inorder.map((v,i)=>[v,i])); // O(1) lookup
let preIdx = 0;
function build(lo, hi) { // lo..hi = range in inorder array
if (lo > hi) return null;
const rootVal = preorder[preIdx++];
const root = new TreeNode(rootVal);
const inIdx = inorderMap.get(rootVal);
root.left = build(lo, inIdx - 1); // left subtree
root.right = build(inIdx + 1, hi); // right subtree
return root;
}
return build(0, inorder.length - 1);
}
// With postorder + inorder: same idea, but take from END of postorder
function buildTreePost(inorder, postorder) {
const inorderMap = new Map(inorder.map((v,i)=>[v,i]));
let postIdx = postorder.length - 1;
function build(lo, hi) {
if (lo > hi) return null;
const rootVal = postorder[postIdx--]; // take from end
const root = new TreeNode(rootVal);
const inIdx = inorderMap.get(rootVal);
root.right = build(inIdx + 1, hi); // RIGHT first (postorder is L-R-root, so reverse)
root.left = build(lo, inIdx - 1);
return root;
}
return build(0, inorder.length - 1);
}Worked Problems
tree-deciduous
Tree construction rules:
- Preorder[0] / Postorder[last] = ROOT of current subtree
- Inorder position of root splits LEFT (before) and RIGHT (after)
- Size of left subtree = inorderIdx - lo
- Always use a HashMap for O(1) inorder lookups
- For postorder: build RIGHT subtree first (reverse root-R-L order)
- For BST: BST property replaces inorder (split at first value > root)
Uniqueness: preorder+inorder or postorder+inorder uniquely determines any binary tree with distinct values. Preorder+postorder only works for full binary trees.
- Preorder[0] / Postorder[last] = ROOT of current subtree
- Inorder position of root splits LEFT (before) and RIGHT (after)
- Size of left subtree = inorderIdx - lo
- Always use a HashMap for O(1) inorder lookups
- For postorder: build RIGHT subtree first (reverse root-R-L order)
- For BST: BST property replaces inorder (split at first value > root)
Uniqueness: preorder+inorder or postorder+inorder uniquely determines any binary tree with distinct values. Preorder+postorder only works for full binary trees.