Validate Binary Search Tree
On this page
Problem statement
Given the root of a binary tree, decide whether it is a valid binary search tree: for every node, all values in its left subtree are strictly smaller and all values in its right subtree are strictly larger. Duplicates are not allowed.
The trap is in the word "all": comparing a node only with its children isn't enough. The fix is to pass down the range each node must fall in. Original problem: LeetCode 98.
Example

Input: [5, 1, 7, null, null, 6, 8]
Output: true
Input: [5, 1, 7, null, null, 4, 8]
Output: false # 4 is in 5's right subtree
Constraints (assumed)
- 1 ≤ nodes ≤ 10,000.
- Values cover the full 32-bit integer range.
What this question tests
- Understanding that the BST rule is about whole subtrees, not just children.
- Passing information down a recursion (bounds), not just returning it up.
- Boundary care: strict inequality and values at the integer limits.
Questions to ask first
- Are duplicates allowed, and on which side? (Here: no duplicates; equal values make it invalid.)
- What range can values take? Full 32-bit range means sentinels like
INT_MINare unsafe. - Is an empty tree valid? (Yes.)
- Recursive is fine? Mention the iterative version for very deep trees.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.