Coding problem · Medium · Trees

Validate Binary Search Tree

Medium Algorithms & data structures Most askedSeen at Amazon, Meta, Microsoft, Bloomberg

Given the root of a binary tree, return true if it is a valid binary search tree: every node's left subtree contains only smaller values, its right subtree only larger values, and both subtrees are BSTs.

Example 1

Input: root = [2,1,3]
Output: true

Example 2

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: 4 is in 5's right subtree but is smaller than 5.

Hints

Hint 1

Comparing a node only with its direct children is not enough.

Hint 2

Pass down an allowed (low, high) range; or check that an in-order traversal is strictly increasing.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(h)

DFS with bounds: the root may be anything; going left tightens the upper bound to the parent's value, going right tightens the lower bound. Any value outside (low, high) breaks the property. Duplicates are invalid (strict inequalities).

Reference solution

function isValidBST(root, low = -Infinity, high = Infinity) {
  if (!root) return true;
  if (root.val <= low || root.val >= high) return false;
  return isValidBST(root.left, low, root.val) && isValidBST(root.right, root.val, high);
}

function isValidBST(root: TreeNode | null, low = -Infinity, high = Infinity): boolean {
  if (!root) return true;
  if (root.val <= low || root.val >= high) return false;
  return isValidBST(root.left, low, root.val) && isValidBST(root.right, root.val, high);
}

def is_valid_bst(root: Optional[TreeNode], low: float = float("-inf"), high: float = float("inf")) -> bool:
    if root is None:
        return True
    if not low < root.val < high:
        return False
    return is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)

<?php

function isValidBST(?TreeNode $root, float $low = -INF, float $high = INF): bool
{
    if ($root === null) {
        return true;
    }
    if ($root->val <= $low || $root->val >= $high) {
        return false;
    }
    return isValidBST($root->left, $low, $root->val) && isValidBST($root->right, $root->val, $high);
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean valid(TreeNode n, long low, long high) {
        if (n == null) return true;
        if (n.val <= low || n.val >= high) return false;
        return valid(n.left, low, n.val) && valid(n.right, n.val, high);
    }
}

Common mistakes

Only checking left.val < node.val < right.val misses violations deeper in the tree ([5,4,6,null,null,3,7]).

Maximum Depth of Binary Tree · Easy
Invert Binary Tree · Easy
Binary Tree Level Order Traversal · Medium
Lowest Common Ancestor of a BST · Medium