Construct Binary Tree from Preorder and Postorder Traversal

Construct Binary Tree from Preorder and Postorder Traversal

What is this problem about?

The Construct Binary Tree from Preorder and Postorder Traversal interview question is unique because, unlike preorder/inorder or postorder/inorder pairs, this specific combination does not always result in a unique binary tree. However, your task is to construct any valid binary tree that matches the given preorder (Root, Left, Right) and postorder (Left, Right, Root) sequences.

Why is this asked in interviews?

Companies like Microsoft and Google use the Construct Binary Tree from Preorder and Postorder Traversal coding problem to test a candidate's ability to handle ambiguity and refine recursive logic. It requires a deeper understanding of how tree traversals relate to each other and how to use the "next" element in a sequence to identify the start of subtrees.

Algorithmic pattern used

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

1. The first element of preorder is the root.
2. The second element of preorder (if it exists) is the root of the left subtree.
3. Find the index of this "left root" in the postorder array.
4. This index defines the boundary of the left subtree in both arrays.
5. Recurse to build the left and right subtrees using the calculated boundaries.

Example explanation

Preorder: [1, 2, 4, 5, 3, 6, 7], Postorder: [4, 5, 2, 6, 7, 3, 1]

1. Root is 1.
2. Next in preorder is 2. This is our left child.
3. In postorder, 2 is at index 2.
4. Left subtree nodes in postorder: [4, 5, 2].
5. Remaining nodes for right subtree: [6, 7, 3].
6. Recurse for node 2 and node 3 as roots of their respective subtrees.

Common mistakes candidates make

• Assuming Uniqueness: Over-complicating the logic by trying to find a "perfect" tree when any valid one will suffice.
• Index Out of Bounds: Not checking if a left child exists before trying to access the second element of the preorder array.
• Incorrect Range Splitting: Miscalculating the subarray sizes when passing indices to the recursive calls.

Interview preparation tip

When dealing with tree construction, always draw out the relationship between the root and its children in both traversal types. Visualizing how the "Left Root" appears at the start of preorder but at the end of its section in postorder is the key to solving this.