Validate Binary Search Tree
Problem statement
You are given the root of a binary tree. Return true if it is a valid binary search tree (BST), and false if it is not.
A tree is a valid BST when, for every node:
- every value in its left subtree is strictly smaller than the node's value,
- every value in its right subtree is strictly larger than the node's value,
- and both subtrees are valid BSTs too.
"Strictly" means equal values are not allowed. Node values can be as small as -2³¹ and as large as 2³¹ - 1, so be careful when you pick "smaller than anything" or "larger than anything" limits.
The tree is written in level order, with null where a child is missing. Think of it as a sanity check on an ordered index — such as a sorted routing table stored as a tree — before you trust lookups on it.
Examples
Example 1
Input: root = [2,1,3]
Output: true
Explanation: 1 is on the left of 2 and is smaller; 3 is on the right and is larger. Both children are leaves, so the tree is valid.

Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: 4 is in the right subtree of 5, so it must be larger than 5, but it is smaller. One broken rule is enough to make the tree invalid.

Hints
[5,4,6,null,null,3,7]: every parent–child pair looks fine, but 3 sits in 5's right subtree.Approach
Optimal: Range check
Intuition
Instead of looking up at the subtrees, pass limits down from the top. The root can hold any value. When you step to a node's left child, that child — and everything below it — must be smaller than the node, so the node's value becomes the new upper limit. When you step right, the node's value becomes the new lower limit.
Each node then only has to check one thing: "is my value strictly between low and high?" The limits carry the information from all ancestors, which is exactly what the simple parent–child check misses. For the starting limits, use values outside the int range (a 64-bit long, or "no limit" in Python), because a node can legally hold -2³¹ or 2³¹ - 1.
Steps
- Call
check(root, low = −∞, high = +∞). - In
check(node, low, high):- If
nodeis empty, returntrue. - If
node.val <= lowornode.val >= high, returnfalse. - Return
check(node.left, low, node.val)andcheck(node.right, node.val, high).
- If
Dry run
root = [5,1,4,null,null,3,6]
| node | allowed range | inside? |
|---|---|---|
| 5 | (−∞, +∞) | yes |
| 1 | (−∞, 5) | yes; no children |
| 4 | (5, +∞) | no → return false |
Nodes 3 and 6 are never visited. Edge cases: a single node with value -2³¹ passes, because the starting limits lie outside the int range. The hint's tree [5,4,6,null,null,3,7] fails at 3, whose range is (5, 6).
Complexity
Time O(n) - Each node is visited exactly once, and each visit does two comparisons. There is no list and no second pass. The walk can also stop early at the first node that breaks the rule. In the worst case (a valid tree) it still visits all n nodes.
Space O(H) - Only the recursion stack is used, one frame per level of the path we are on. H is O(log n) for a balanced tree and O(n) for a line-shaped one. No list of values is stored. The input tree is not counted.
from collections import deque
from typing import Optional
# Definition for a binary tree node (LeetCode's).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def check(node: Optional[TreeNode], low: float, high: float) -> bool:
if node is None:
return True
if node.val <= low or node.val >= high:
return False
return check(node.left, low, node.val) and check(node.right, node.val, high)
return check(root, float("-inf"), float("inf"))
def build_tree(values: list) -> Optional[TreeNode]:
"""Build a tree from level-order values, None = missing child."""
if not values or values[0] is None:
return None
root = TreeNode(values[0])
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
if i < len(values) and values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
if __name__ == "__main__":
print(str(Solution().isValidBST(build_tree([2, 1, 3]))).lower()) # true
print(str(Solution().isValidBST(build_tree([5, 1, 4, None, None, 3, 6]))).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: "is this binary tree a valid BST?" — a rule that holds for whole subtrees, not just children
- Idea: pass a range
(low, high)down the tree; going left the node becomeshigh, going right it becomeslow - Cost: O(n) time, O(H) space for the recursion
- Trap: only comparing a node with its children misses
[5,4,6,null,null,3,7]; and int limits break on values equal toINT_MIN/INT_MAX— uselongor "no limit" - Remember: in-order of a valid BST is strictly increasing — checking that is an equal alternative
Interview follow-ups
Do it without recursion.
Use an explicit stack for an iterative in-order walk: go as far left as you can pushing nodes, pop one, compare it with the previous value, then move to its right child. Stop with
falsethe moment a value is not larger than the previous one. Time stays O(n) and the stack holds O(H) nodes, but a very deep tree can no longer overflow the call stack.The tree is valid except that two nodes were swapped by mistake. How do you find them?
Do an in-order walk and look for places where a value is smaller than the one before it. If the swapped nodes were next to each other there is one such drop; otherwise there are two. The first wrong node is the larger value at the first drop, and the second is the smaller value at the last drop. This is the classic "Recover Binary Search Tree" problem and costs O(n) time.
The tree can have duplicates, and duplicates must go to the left. What changes?
Only the comparisons. With the range check, the left side allows
node.val == high, so the test becomesnode.val <= low or node.val > high. Everything else — the walk, the time and the space — stays the same. State the rule before you code, because interviewers often leave it vague on purpose.
Frequently asked questions
Because the BST rule is about whole subtrees, not just direct children. In [5,4,6,null,null,3,7], node 6 has children 3 and 7, and 3 < 6 < 7 looks fine. But 3 is in the right subtree of 5, so it must be larger than 5. Only a check that carries limits from all ancestors (or an in-order check) catches this.
Node values can be exactly Integer.MIN_VALUE or Integer.MAX_VALUE. If you start with int limits, a single node holding Integer.MIN_VALUE would fail the node.val <= low check even though it's valid. A 64-bit long starts strictly outside the int range, so every real value fits. Another option is to pass null for "no limit".
Yes. Keep only the previous value you visited (starting as "none"). During the in-order walk, if the current value is <= the previous one, return false; otherwise update the previous value. That has the same O(n) time and O(H) space as the range check, so it is also an optimal solution — pick whichever you find easier to explain.
Not in this problem: both sides must be strictly smaller or larger. Some real BSTs allow duplicates on one side (for example, equal keys always go right). In that case, change the matching comparison from >= to > (or <= to <) on that side only, and say which rule you picked out loud in the interview.
Sorted structures back a lot of infra: ordered indexes, interval maps for IP ranges, and sorted routing tables. A check like this is how you catch a corrupted or badly built index before it gives wrong lookups. It is also a quick test of whether you understand that a rule on "the whole subtree" needs information passed down from ancestors.
