Reconstruct a BST from Preorder Traversal
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
Given the preorder traversal of a binary search tree containing unique integers, reconstruct the tree and return its root.
### Function Contract
Implement `bstFromPreorder(preorder)`.
### Constraints & Assumptions
- `0 <= len(preorder) <= 100,000`.
- Values are unique signed 32-bit integers.
- The input is guaranteed to be a valid preorder traversal of some BST.
- Return `null` for an empty traversal.
### Clarifying Questions to Ask
- Are values unique? Yes.
- Must the output tree be balanced? No; reproduce the represented BST.
- Is sorting allowed? It is unnecessary and would lose the intended linear-time target.
- Can the tree be completely skewed? Yes, so recursion depth matters.
```hint Use unresolved ancestors
Maintain a stack of nodes whose right subtree has not yet been attached. A smaller value becomes the left child of the stack top; a larger value pops completed ancestors.
```
```hint The last popped node is the parent
When a value is greater than several stack tops, its parent is the final ancestor removed before the stack becomes compatible.
```
### Example
```text
preorder = [8, 5, 1, 7, 10, 12]
result:
8
/ \
5 10
/ \ \
1 7 12
```
### Evaluation Focus
- Consumes the traversal in one pass.
- Attaches left and right children to the correct ancestors.
- Handles monotonic input without recursion overflow.
- Runs in `O(n)` time and `O(h)` auxiliary space.
### Extensions to Discuss
1. How would lower and upper bounds support a recursive construction?
2. How would duplicates change the attachment rules?
3. How could you validate an untrusted preorder while constructing?
Overview: Reconstruct the exact binary search tree represented by a preorder traversal of unique integers. Handle empty and completely skewed inputs at scale while preserving the intended tree rather than balancing it.
Community answers
Answer by jimmyp
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def bstFromPreorder(preorder: list[int]) -> TreeNode | None:
if not preorder:
return None
root = TreeNode(preorder[0])
stack = [root] # stack of "unresolved ancestors" — nodes that might still need a right child
for val in preorder[1:]:
node = TreeNode(val)
if val < stack[-1].val:
# val belongs in the left subtree of the current top ancestor
stack[-1].left = node
else:
# val is bigger than the top: pop off all ancestors smaller than val,
# since node's parent is the last (deepest) ancestor it's still greater than
last = None
while stack and stack[-1].val < val:
last = stack.pop()
last.right = node
stack.append(node)
return root