On this page

Validate Binary Search Tree

Given the root of a binary tree, determine whether it is a valid binary search tree: for every node, all values in the left subtree are strictly less and all values in the right subtree are strictly greater than the node's value.

Constraints:

  • The number of nodes is in the range [1, 10^4].
  • -2^31 <= Node.val <= 2^31 - 1

Intuition

1 5
2 / \
3 1 4
4 / \
5 3 6

This tree is not a BST, even though every node is bigger than its left child and smaller than its right child. Node 3 sits in the right subtree of 5, but 3 is smaller than 5.

So checking a node only against its direct children is not enough. Every node must fit inside a range set by all of its ancestors.

Approach: Pass Down an Allowed Range

Each node carries an allowed open interval (low, high).

  1. The root may take any value, so start with (-infinity, +infinity).
  2. A node is valid only if low < node.val < high. Otherwise return false.
  3. Going left, the new upper bound becomes the node's value: (low, node.val).
  4. Going right, the new lower bound becomes the node's value: (node.val, high).
  5. A null node is valid.

The bounds must be wider than 32-bit integers (use long in C++ and Java), because node values can equal INT_MIN or INT_MAX.

An alternative is to do an inorder traversal and check that the values are strictly increasing.

Code

class Solution {
bool check(TreeNode* node, long long low, long long high) {
if (node == nullptr) return true;
if (node->val <= low || node->val >= high) return false;
return check(node->left, low, node->val) &&
check(node->right, node->val, high);
}
public:
bool isValidBST(TreeNode* root) {
return check(root, LLONG_MIN, LLONG_MAX);
}
};

Complexity

Time: O(n)

Each node is checked once.

Space: O(h)

Recursion stack depth equals the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Checking a node only against its children is not enough, because a node deep in the right subtree must still be larger than the root. So I pass down an allowed range. The root can be anything. When I go left, the node value becomes the new upper bound, and when I go right, it becomes the new lower bound. A node is valid only if its value is strictly between the bounds. I use long types, or infinities, for the initial bounds, so values equal to the integer limits still work. Time is O of n and space is O of h. An equivalent approach is an inorder traversal that checks the values are strictly increasing."
Next TopicLowest Common Ancestor of a Binary Search Tree