DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Validate Binary Search Tree

mediumTrees Must-do

Problem statement

Given the root of a binary tree, decide whether it is a valid binary search tree (BST). In a valid BST, for every node:

  • every value in its left subtree is strictly smaller than the node's value, and
  • every value in its right subtree is strictly larger.

The rule applies to whole subtrees, not just direct children. Equal values are not allowed. An empty tree is valid. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [8, 4, 12, 2, 6]

Output: true

Example 2

Input: root = [8, 4, 12, 2, 9]

Output: false

Explanation: 9 is a correct right child of 4, but it sits in 8's left subtree and is larger than 8.

Hints

Approach

Carry the allowed range down the tree. Every node must lie strictly inside (low, high), where the bounds come from its ancestors.

  1. valid(node, low, high): an empty node is valid.
  2. If node.val <= low or node.val >= high, return false.
  3. Recurse left with (low, node.val) and right with (node.val, high).
  4. Start with no bounds at all.

Going left, the current node becomes the new upper limit for everything below; going right, it becomes the new lower limit. This checks every whole-subtree constraint using only the path from the root, stops at the first violation, and needs no list. In Java, use long bounds (or nullable ones) so a node holding Integer.MAX_VALUE is not wrongly rejected.

ComplexityTime O(n)Space O(h)
Python
from typing import Optional
# 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 valid(node, low: float, high: float) -> bool:
if node is None:
return True
if not (low < node.val < high):
return False
return valid(node.left, low, node.val) and valid(node.right, node.val, high)
return valid(root, float("-inf"), float("inf"))

Follow-up questions

  • Do the in-order check without a list, keeping only the previous value.
  • Two nodes of a BST were swapped by mistake. Find them and fix the tree.

Frequently asked questions

The BST rule covers whole subtrees. In [8, 4, 12, 2, 9], every parent-child pair looks fine, but 9 is in the left subtree of 8 and is larger than it. The bounds approach catches this because 9 inherits the upper limit 8.

If you start with Integer.MIN_VALUE and Integer.MAX_VALUE as bounds, a tree with a single node of value Integer.MAX_VALUE fails the strict check val < high. Starting from Long limits, or using null to mean no bound, avoids that.

Ordered indexes, such as the B-trees behind databases and some key-value stores, rely on this invariant. Checking it is a model for validating any structure whose correctness depends on ancestors, not just neighbours, like nested config where a child setting must stay within its parent's limits.