Watch 10 video solutions for Construct Binary Search Tree from Preorder Traversal, a medium level problem involving Array, Stack, Tree. This walkthrough by Techdose has 60,648 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.
Example 1:
Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3] Output: [1,null,3]
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 1000preorder are unique.Problem Overview: Given an array representing the preorder traversal of a Binary Search Tree, reconstruct the original BST and return its root. The preorder order guarantees that every node appears before its left and right subtree, while BST rules ensure left < root < right.
Approach 1: Recursive Insertion (Time: O(n^2), Space: O(h))
This approach builds the tree the same way values would be inserted into a normal BST. Iterate through the preorder array and insert each value into the tree using a recursive BST insert routine. For every insertion, traverse left or right depending on the value comparison until you find the correct position. The logic is simple and mirrors standard BST operations, which makes it easy to implement during interviews. The drawback is performance: if the preorder array is sorted, the BST becomes skewed and each insertion scans most of the tree, resulting in O(n^2) time.
Approach 2: Stack-based Iterative Construction (Time: O(n), Space: O(n))
This optimized method uses a stack to track the path of nodes whose right child hasn't been assigned yet. Start by creating the root from the first preorder value and push it onto the stack. For each next value, check the top of the stack. If the value is smaller, it becomes the left child of the top node. If the value is larger, pop nodes until you find the correct parent where the value should be attached as the right child. The stack maintains a decreasing sequence of ancestors, similar to a monotonic stack. Each element is pushed and popped at most once, giving O(n) time complexity.
The key insight comes from preorder traversal properties: nodes appear in root-left-right order, so once you encounter a value greater than a node, you've finished that node's left subtree and are moving to the right subtree. The stack efficiently tracks this transition.
Recommended for interviews: Interviewers typically expect the O(n) stack solution because it demonstrates understanding of preorder traversal constraints and Binary Search Tree structure. The recursive insertion approach still helps show baseline reasoning and correctness before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Insertion | O(n^2) worst case | O(h) | Simple implementation when demonstrating BST insertion logic |
| Stack-based Iterative Construction | O(n) | O(n) | Optimal solution for large inputs and interview expectations |