#105 Construct Binary Tree from Preorder and Inorder Traversal
frequently reported atByteDance / TikTokAdobeBloombergAmazonMicrosoftGoogle
the problem
In plain words
Given the preorder and inorder traversals of a tree with unique values, rebuild the tree and return its root.
in preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
out [3,9,20,null,null,15,7]
in preorder = [-1], inorder = [-1]
out [-1]
- 1 ≤ n ≤ 3000
- -3000 ≤ value ≤ 3000
- Values are unique
- Both arrays describe the same tree
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBuild a tree from traversalsDivide and conquer
Preorder tells you who the root is (the next unused value). Inorder tells you what's left and right of it. Recurse on each side.
solutions
From brute force to optimal
Take the root from preorder, scan inorder to find it, split, recurse.
- root = preorder[preStart].
- Scan inorder[lo..hi] for root → mid.
- Left size = mid − lo; recurse on both halves.
Each of n roots scans up to n inorder slots (skewed tree); O(n log n) when balanced.
Recursion stack; no array copies.
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder, 0, inorder, 0, inorder.length - 1); } /** Root is preorder[preStart]; the subtree's values are inorder[lo..hi]. */ private TreeNode build(int[] preorder, int preStart, int[] inorder, int lo, int hi) { if (lo > hi) return null; TreeNode root = new TreeNode(preorder[preStart]); int mid = lo; while (inorder[mid] != root.val) mid++; // O(n) scan for the root int leftSize = mid - lo; root.left = build(preorder, preStart + 1, inorder, lo, mid - 1); root.right = build(preorder, preStart + 1 + leftSize, inorder, mid + 1, hi); return root; }}Precompute every value's inorder position so finding the root is O(1).
- Map each inorder value to its index.
- Keep a running pointer into preorder.
- build(lo, hi): root = preorder[next++]; mid = map.get(root); build left (lo, mid−1) then right (mid+1, hi).
Each node is created once with an O(1) lookup.
The map, plus O(h) recursion.
class Solution { private int next; // next unused preorder position private Map<Integer, Integer> indexOf; public TreeNode buildTree(int[] preorder, int[] inorder) { indexOf = new HashMap<>(); for (int i = 0; i < inorder.length; i++) indexOf.put(inorder[i], i); // O(1) root lookup next = 0; return build(preorder, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int lo, int hi) { if (lo > hi) return null; TreeNode root = new TreeNode(preorder[next++]); // preorder: root comes first int mid = indexOf.get(root.val); // inorder: left | root | right root.left = build(preorder, lo, mid - 1); // build left FIRST: it is next in preorder root.right = build(preorder, mid + 1, hi); return root; }}in the room
How to say it in the interview
talk track
- Draw preorder = [root | left… | right…] and inorder = [left… | root | right…] — the picture is the explanation.
- Point out why the left subtree must be built first: it's next in preorder.
traps
- Building the right subtree before the left with the running preorder pointer — the order of tokens no longer matches.
- Copying subarrays with
Arrays.copyOfRangein every call: O(n²) time and memory.
what they ask next
Follow-ups
From inorder and postorder (LC 106)?
Postorder ends with the root: walk it backwards and build the right subtree first.
Why must values be unique?
Duplicates make the root's position in inorder ambiguous, so the tree isn't uniquely determined.
before you submit
Edge cases to test
- One node → that node.
- Only left children: inorder is preorder reversed.
- Only right children: inorder equals preorder.
practise next
Similar problems
- #106Construct Binary Tree from Inorder and Postorder TraversalMediumin Tree Recursion
- #297Serialize and Deserialize Binary TreeHardin Traversals
- #108