Construct Binary Tree from Inorder and Postorder Traversal

Construct Binary Tree from Inorder and Postorder Traversal

What is this problem about?

The Construct Binary Tree from Inorder and Postorder Traversal interview question is a standard tree reconstruction task. You are given two arrays: inorder (Left, Root, Right) and postorder (Left, Right, Root). Your goal is to return the unique binary tree that produces these two traversals.

Why is this asked in interviews?

This is a classic problem at Amazon and Bloomberg because it tests recursive thinking and spatial visualization. The Construct Binary Tree from Inorder and Postorder Traversal coding problem requires identifying how the root of a tree (found easily in postorder) splits the inorder array into left and right sub-problems.

Algorithmic pattern used

This utilizes the Array, Divide and Conquer, Hash Table, Binary Tree interview pattern.

1. The last element of the postorder array is always the root of the current subtree.
2. Find the index of this root in the inorder array.
3. Elements to the left of this index in inorder form the left subtree; elements to the right form the right subtree.
4. Recursively apply this logic to the sub-arrays.

Example explanation

Inorder: [9, 3, 15, 20, 7], Postorder: [9, 15, 7, 20, 3]

1. Postorder's last element is 3. Root = 3.
2. In Inorder, 3 is at index 1.
3. Left of 3 in Inorder: [9]. Right of 3 in Inorder: [15, 20, 7].
4. Now, rebuild the right subtree using Postorder [15, 7, 20] and Inorder [15, 20, 7].
5. Root of right subtree is 20 (last in Postorder segment).

Common mistakes candidates make

• Inefficient Lookups: Searching for the root in the inorder array using a linear scan in every recursive call, resulting in O(N^2) time. Using a Hash Map to pre-store inorder indices reduces this to O(N).
• Array Slicing: Creating new copies of sub-arrays in every call, which increases space complexity. It's better to pass start and end indices.
• Traversal Order: Getting the order of recursive calls wrong. In this problem, you must construct the right subtree before the left subtree because we are reading the postorder array from back to front.

Interview preparation tip

Always suggest using a Hash Map for the inorder index lookups immediately. It shows you are proactively thinking about time complexity.