Validate a Binary Search Tree Iteratively
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
Determine whether a binary tree is a valid binary search tree. Every value in a node's entire left subtree must be smaller than the node value, and every value in the entire right subtree must be greater. Implement the validation iteratively.
### Function Contract
Implement `isValidBST(root)`.
### Constraints & Assumptions
- The tree contains at most `100,000` nodes.
- Node values are signed 64-bit integers and are intended to be unique in a valid tree.
- The input is an acyclic binary tree.
- Return `true` for an empty tree.
### Clarifying Questions to Ask
- Are duplicates allowed in a valid BST? No.
- Is checking each node against only its parent enough? No; ancestor bounds apply to the whole subtree.
- Must the solution avoid recursion? Yes.
- Can a bound be outside the node value type? Use absent bounds or a wider representation rather than unsafe sentinels.
```hint Carry ancestor bounds
Put `(node, lowerExclusive, upperExclusive)` frames on a stack. Children inherit one bound and tighten the other.
```
### Example
```text
tree = [5, 1, 7, null, null, 4, 8]
output = false
```
Although `4 < 7`, it lies in the right subtree of `5` and violates the inherited lower bound.
### Evaluation Focus
- Enforces strict whole-subtree bounds.
- Handles minimum and maximum integer values safely.
- Avoids recursion overflow on a skewed tree.
- Runs in `O(n)` time with `O(h)` stack space.
### Extensions to Discuss
1. How would an iterative inorder traversal validate the tree?
2. What changes if duplicates are permitted only on the right?
3. How would you report the first violating node and bound?
Overview: Validate a binary tree iteratively against the full binary-search-tree ordering rule, not only parent-child comparisons. Reject duplicates and nonlocal ordering violations while handling empty, deep, and extreme 64-bit-value trees safely.
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