Validate a Binary Search Tree: How to Explain the Bounds Approach in a Coding Interview
3 views
"Given the root of a binary tree, determine whether it is a valid binary search tree" is one of the most common tree questions in phone screens and onsite rounds. It looks simple, and that is exactly why interviewers like it: the obvious first idea is wrong, and they want to see whether you catch it.
The trap: only comparing parent and child
Many candidates start by checking that every node's left child is smaller and its right child is larger. That check passes for this tree, which is not a valid BST:
10
/ \
5 15
/ \
6 20
Node 6 is a valid left child of 15, but it sits in the right subtree of 10, so it must be greater than 10. The BST property is about whole subtrees, not just direct children. Saying this out loud early, ideally with a small counterexample like the one above, shows the interviewer you understand the definition rather than a pattern.
Approach 1: pass down a valid range
Every node has an allowed interval (low, high). The root can be anything. When you move left, the current value becomes the new upper bound; when you move right, it becomes the new lower bound.
def is_valid(node, low=float('-inf'), high=float('inf')):
if node is None:
return True
if not (low < node.val < high):
return False
return (is_valid(node.left, low, node.val) and
is_valid(node.right, node.val, high))
Time is O(n) because each node is visited once, and space is O(h) for the recursion stack, where h is the height of the tree. Mention that h can be n for a skewed tree, which matters if the interviewer asks about very deep inputs. In that case you can offer an iterative version with an explicit stack of (node, low, high) tuples.
Approach 2: in-order traversal must be strictly increasing
An in-order traversal of a BST visits values in sorted order. So you can walk the tree in-order and keep only the previous value; if the current value is not strictly greater, return False. This uses the same O(n) time and O(h) space, and it is a nice second solution to mention because it shows you can connect a structural property to a traversal order.
Edge cases worth naming
- Duplicates: ask whether equal values are allowed and on which side. The code above treats duplicates as invalid.
- Integer limits: if a node can hold the minimum or maximum integer value, using infinity (or None) as the initial bounds avoids a false rejection. In Java or C++, people often get burned by using Integer.MIN_VALUE as a sentinel.
- Empty tree: usually considered valid.
How to talk through it
A clean structure is: restate the definition, give the counterexample that breaks the naive approach, describe the bounds idea in one sentence, code it, then trace it on the counterexample to show node 6 fails because its range is (10, 15). Finish with complexity and the follow-up about iteration or duplicates. Interviewers care at least as much about this narration as about the final code.
Practicing under real conditions
Knowing the solution at your desk and explaining it while someone watches are different skills. Mock interviews help, and some candidates also use tools such as Linkjob AI (https://linkjob.ai), which gives real-time help during live job interviews and technical interviews, to stay organized when nerves make it hard to remember edge cases. Whatever you use, practice saying the reasoning out loud until the counterexample and the bounds explanation come naturally.