Coding · Trees
Construct Binary Tree from Inorder and Postorder
- Reported once
- Medium
- intern
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You are given the inorder and the postorder traversal of the same binary tree, where all values are distinct. Rebuild the tree and return it as a level-order array, writing null for a missing child and dropping trailing nulls. For inorder [9,3,15,20,7] and postorder [9,15,7,20,3] the answer is [3,9,20,null,null,15,7]. There are up to 3,000 nodes, and an empty tree gives an empty array.
Restated in our own words, not a quote from Juspay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
First, are all values distinct? The whole method depends on it, so I would ask and assume yes. Then: do the two arrays really describe one tree, or must I validate that? Can the input be empty? How many nodes are there, which tells me whether recursion depth is a risk? And what output form does the caller want: a tree object, or a level-order list with null for gaps?
Assumptions I would state: distinct values, both arrays are valid traversals of the same tree, up to 3,000 nodes, an empty input gives an empty tree, and the answer is a level-order array with trailing nulls removed.
Brute force
Say the obvious answer and why it is too slow.
The plain version takes the last postorder value as the root, finds it in the inorder array with a linear search, slices both arrays into a left part and a right part, and recurses on the slices.
It is correct and short. The price is time and memory: each level does an O(n) search and copies O(n) elements into slices. On a balanced tree that totals O(n log n). On a skewed tree, where every node has only one child, the arrays shrink by one each time, so the total is n plus n minus 1 plus n minus 2 and so on, which is O(n²). With 3,000 nodes that is millions of copied numbers, and it grows quickly beyond that. Both the search and the copying are avoidable.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(n)
The pattern is divide and conquer with an index map. Two facts do all the work. In postorder the last value is always the root of the current tree. In inorder, everything left of the root belongs to the left subtree and everything right of it belongs to the right subtree.
So the root's position in the inorder array splits the problem into two smaller ones. To find that position in O(1), build a map from value to inorder index once, which is allowed because values are distinct. To avoid slicing, pass only a window into the inorder array, a low and a high index.
The postorder array is consumed from the back with a single moving index. Postorder reads left subtree, right subtree, root, so reading it backwards gives root, right subtree, left subtree. That fixes the order of the recursion: after taking the root, build the right child first, then the left child. If you build the left first, you read the wrong values.
Why is it correct? Each call is given the window of inorder positions that holds exactly one subtree, and the next unread value from the back of postorder is that subtree's root. Splitting at the root's inorder index hands each child exactly its own window, and the backwards reading order ensures the right subtree uses up its values before the left starts.
Out loud: "Root from the back of postorder, split by the inorder index map, right before left."
Walk it through
A dry run on the example, step by step.
| Step | Next from back | Inorder window | Split at | Creates |
|---|---|---|---|---|
| 1 | 3 | 0 to 4 | 1 | root 3 |
| 2 | 20 | 2 to 4 | 3 | right child of 3 |
| 3 | 7 | 4 to 4 | 4 | right child of 20 |
| 4 | 15 | 2 to 2 | 2 | left child of 20 |
| 5 | 9 | 0 to 0 | 0 | left child of 3 |
Take inorder [9,3,15,20,7] and postorder [9,15,7,20,3]. The table lists the nodes in the order they are created.
The back of postorder is 3, which sits at inorder index 1, so the window 0 to 4 splits into a left window (0 to 0) and a right window (2 to 4). We build right first: the next value from the back is 20, at index 3, splitting 2 to 4 into 2 to 2 and 4 to 4. Again right first: the next value is 7, with empty windows on both sides. Then the left child of 20: the next value is 15. Finally the left child of 3: the next value is 9. The creation order is 3, 20, 7, 15, 9, and reading the finished tree level by level gives the answer.
The code
Runnable JavaScript, checked against test cases.
function buildTree(inorder, postorder) {
const inorderIndex = new Map();
inorder.forEach((value, i) => inorderIndex.set(value, i));
let postIndex = postorder.length - 1;
function build(low, high) {
if (low > high) return null;
const value = postorder[postIndex--];
const node = { value, left: null, right: null };
const split = inorderIndex.get(value);
node.right = build(split + 1, high);
node.left = build(low, split - 1);
return node;
}
const root = build(0, inorder.length - 1);
const levels = [];
const queue = [root];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
levels.push(node === null ? null : node.value);
if (node !== null) queue.push(node.left, node.right);
}
while (levels.length > 0 && levels[levels.length - 1] === null) levels.pop();
return levels;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty input: the first call has low above high and returns no node, so the level-order array is empty.
- One node: the root splits into two empty windows.
- Left-skewed tree: the inorder and postorder arrays are equal, and the recursion goes one level deeper per node.
- Right-skewed tree: postorder is inorder reversed.
- Negative values and zero: only map lookups and comparisons of indexes are used, so the values do not matter.
- Trailing nulls: the output loop trims them, so a leaf at the bottom does not leave padding.
- Depth: a chain of 3,000 nodes means 3,000 nested calls, which JavaScript allows.
Follow-ups to expect
Where the interviewer pushes next.
- How would you build the tree from preorder and inorder instead, and which side do you build first?
- Why can a tree not be rebuilt from preorder and postorder alone when a node can have a single child?
- How would you remove the recursion so a degenerate tree of a million nodes cannot overflow the stack?
- What goes wrong if the values are not distinct, and what extra information would you need?
- How would you check that the two arrays are consistent traversals before building?
Where candidates slip
The mistakes this problem punishes.
The classic mistake is building the left child before the right one. Reading postorder from the back gives root, right, left, so the order of the two recursive calls matters.
- Slicing the arrays on every call, which turns a linear solution into a quadratic one.
- Searching for the root with indexOf on every call instead of building the map once.
- Passing the wrong bounds, for example mid instead of mid plus one for the right window.
- Moving the postorder index inside the wrong branch, so it is shared incorrectly.
- Forgetting to trim trailing nulls when printing the level order.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.