Construct Binary Search Tree from Preorder Traversal

Construct Binary Search Tree from Preorder Traversal

What is this problem about?

The Construct Binary Search Tree from Preorder Traversal interview question asks you to rebuild a BST given only its preorder traversal sequence. In a preorder traversal, the nodes are visited in the order: Root, Left Subtree, Right Subtree. Since the input is a BST, we also know that for any node, all left descendants are smaller and all right descendants are larger.

Why is this asked in interviews?

Companies like Microsoft and Meta use this Construct Binary Search Tree from Preorder Traversal coding problem to test a candidate's understanding of tree properties. It specifically evaluates if you can leverage the inherent sorted nature of BSTs to avoid the need for an inorder traversal, which is usually required for general binary trees.

Algorithmic pattern used

This follows the Array, Monotonic Stack, Binary Search Tree interview pattern. There are two efficient ways to solve this:

1. Recursive with Bounds: Pass a min and max limit to each recursive call. If the current value in the preorder array fits within the bounds, create a node and recurse.
2. Iterative with Stack: Use a stack to keep track of the path. If the next value is smaller than the stack top, it's a left child. If it's larger, pop until you find the parent it belongs to as a right child.

Example explanation

Preorder: [8, 5, 1, 7, 10, 12]

1. Root is 8.
2. 5 is less than 8, so it goes to the left of 8.
3. 1 is less than 5, so it goes to the left of 5.
4. 7 is greater than 5 but less than 8, so it becomes the right child of 5.
5. 10 is greater than 8, so it becomes the right child of 8.
6. 12 is greater than 10, so it becomes the right child of 10.

Common mistakes candidates make

• Sorting the array: Some candidates sort the preorder array to get the inorder sequence and then solve it like a general tree problem. While correct, it takes O(N log N) instead of the O(N) bound-based approach.
• N^2 Recursion: Finding the first element larger than the root to split left and right subtrees in every call, which leads to O(N^2) in skewed trees.
• Null handling: Not correctly handling the base case when the preorder array is empty or the current value doesn't fit the subtree bounds.

Interview preparation tip

For BST construction problems, always try to use the range-based recursion technique. It's concise and demonstrates a deep understanding of the "Search" property in Binary Search Trees.