Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

What is this problem about?

The Construct Binary Tree from Preorder and Inorder Traversal interview question asks you to build a binary tree given its preorder traversal (Root, Left, Right) and inorder traversal (Left, Root, Right). Like its postorder counterpart, this combination provides enough information to uniquely identify the tree structure.

Why is this asked in interviews?

Companies like Google, Apple, and Adobe use this Construct Binary Tree from Preorder and Inorder Traversal coding problem to test a candidate's ability to manage pointers and indices under recursion. It evaluates how well you can break a large problem into identical sub-problems by locating the root and dividing the data.

Algorithmic pattern used

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

1. The first element of the preorder array is the root.
2. Locate this root in the inorder array to find the boundary between left and right subtrees.
3. Recurse for the left and right sub-arrays.
4. Use a Hash Map to store inorder indices for O(1) root location.

Example explanation

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

1. First in Preorder is 3. Root = 3.
2. In Inorder, 3 is at index 1.
3. Elements left of index 1 in Inorder [9] are the left subtree.
4. Elements right of index 1 in Inorder [15, 20, 7] are the right subtree.
5. In Preorder, the element after 3 is the root of the left subtree (9). The elements after the left subtree are the right subtree.

Common mistakes candidates make

• Incorrect pointer math: Miscalculating the boundaries of the sub-arrays in the preorder list based on the size of the left subtree in the inorder list.
• Global variables: Relying on global variables to track the current index in the preorder array, which can be messy. It's cleaner to pass it by reference or as part of an object.
• Base cases: Not properly identifying when a sub-array is empty (e.g., start > end), which leads to infinite recursion.

Interview preparation tip

Tree construction problems are recursive by nature. Practice writing the solution without helper functions like Arrays.copyOfRange to ensure you can manage raw array indices, as this is often required in high-performance coding environments.