Construct a BT from Preorder and Inorder
HardPreorder gives the root, inorder splits the sides
Problem
Build a binary tree from its preorder and inorder traversals.
Preorder gives the root; its spot in inorder splits left and right subtrees — recurse on each.
The idea
The first preorder value is the root; finding it in the inorder array splits that array into the left and right subtrees and tells you their sizes. A hash map from value to inorder index makes each lookup O(1), so the build is O(n).
The trick
- Index the inorder positions in a map first, or the build is O(n²).
- The left subtree's size determines how much of the preorder belongs to it.
- Requires distinct values.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — pre=[3,9,20,15,7], in=[9,3,15,20,7] Values: 3, 9, 20, 15, 7.
1root = pre[0]; find it in inorder at index m2left = build(pre[1..m], in[0..m-1]); right = build(rest)Input
- array
- [3, 9, 20, 15, 7]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
- Output:
- [[3], [9, 20], [15, 7]]
- Explanation:
- Rebuild the exact tree.
Example 2
- Input:
- preorder = [1,2], inorder = [2,1]
- Output:
- [[1], [2]]
- Explanation:
- 2 is the left child of 1.
Example 3
- Input:
- preorder = [1], inorder = [1]
- Output:
- [[1]]
- Explanation:
- Single node.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.