How do you validate if a binary tree is a valid Binary Search Tree?
This problem requires checking if a binary tree satisfies the BST property where left children are smaller and right children are larger than the parent. It tests recursion and range constraints.
Why Interviewers Ask This
Interviewers ask this to test deep understanding of BST properties beyond simple comparisons. They want to see if you realize that a node must be within a valid range defined by its ancestors, not just its immediate parent. It demonstrates recursive thinking and constraint propagation.
How to Answer This Question
Explain that a simple parent-child comparison is insufficient. Define a valid range (min, max) for each node. Initially, the root can be any value (-infinity, +infinity). For the left child, the max becomes the parent's value; for the right child, the min becomes the parent's value. Recursively check if each node falls within its allowed range. Return true only if all nodes satisfy their constraints.
Key Points to Cover
- Range validation logic
- Recursive descent
- Ancestor constraints
- Strict inequality handling
Sample Answer
To validate a BST, I cannot just compare a node with its immediate children. I need to ensure every node lies within a specific range determined by its ancestors. I start with the root having a range of negative infinity…
Common Mistakes to Avoid
- Only comparing with immediate parent
- Using <= instead of < for duplicates
- Forgetting to update bounds correctly for subtrees
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.