Obsidian Notes

11. Validate Binary Search Tree

4 min read

Description

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys strictly less than the node’s key.
  • The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

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

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node’s value is 5 but its right child’s value is 4.

Constraints:

  • The number of nodes in the tree is in the range [1, 104].
  • -231 <= Node.val <= 231 - 1

Approach - Recursion

  • It should be strictly less and greater so equal values not allowed
  • we go left so we update the max to current value
  • Time: O(n) Space: O(n)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
 
    public boolean valid(TreeNode n, long min, long max) {
        if (n == null) return true;
        if (n.val <= min || n.val >= max) return false;
        return valid(n.left, min, n.val) && valid(n.right, n.val, max);
    }
}

Primary Approach: Recursive Range DFS ( Time, Space)

Intuition

Checking only immediate children (node.left.val < node.val < node.right.val) is a classic trap because it misses ancestor constraints. Every node must fall strictly within a dynamic valid range (min, max) passed down from its parent and ancestors:

  1. Initialize the range boundaries using Long.MIN_VALUE and Long.MAX_VALUE to cleanly handle node values that equal Integer.MIN_VALUE or Integer.MAX_VALUE.
  2. Base Case: An empty subtree (node == null) is valid, so return true.
  3. Validation: If node.val <= min or node.val >= max, the BST invariant is broken; return false.
  4. Subtrees:
    • Left Subtree: Values must be strictly less than node.val set max = node.val.
    • Right Subtree: Values must be strictly greater than node.val set min = node.val.
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
 
    private boolean isValid(TreeNode node, long min, long max) {
        if (node == null) return true;
 
        // Node value must lie strictly within (min, max)
        if (node.val <= min || node.val >= max) return false;
 
        // Left child max bound becomes node.val; Right child min bound becomes node.val
        return isValid(node.left, min, node.val) && isValid(node.right, node.val, max);
    }
}

Complexity

  • Time Complexity: — Every node in the binary tree is visited once.
  • Space Complexity: — Auxiliary call stack space bounded by tree height ( for balanced, for skewed).

Alternative Approach: Inorder Traversal ( Time, Space)

Intuition

An inorder traversal () of a valid BST must yield strictly increasing values:

  1. Maintain a prev pointer tracking the previously visited node in the inorder sequence.
  2. Recursively visit the left subtree first.
  3. Check if prev != null && node.val <= prev.val. If true, the tree is invalid.
  4. Set prev = node and recursively check the right subtree.
class Solution {
    private TreeNode prev = null;
 
    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }
 
    private boolean inorder(TreeNode node) {
        if (node == null) return true;
 
        // 1. Visit left subtree
        if (!inorder(node.left)) return false;
 
        // 2. Validate current node against previous inorder value
        if (prev != null && node.val <= prev.val) return false;
        prev = node;
 
        // 3. Visit right subtree
        return inorder(node.right);
    }
}

Complexity

  • Time Complexity: — Every node is visited once in inorder sequence.
  • Space Complexity: — Call stack depth bounded by tree height .

Key Interview Discussion Points

  • The Local Check Trap: Point out that checking only node.left and node.right fails. For example, in [5, 1, 6, null, null, 3, 7], node 3 is locally valid as the left child of 6, but invalid because it resides in the right subtree of 5.
  • Integer Boundary Edge Case: Mention that using long parameters (Long.MIN_VALUE, Long.MAX_VALUE) prevents overflow/underflow failures when tree nodes contain values equal to Integer.MIN_VALUE or Integer.MAX_VALUE.

Easy Memory Rule

“Pass (min, node.val) to Left Subtree Pass (node.val, max) to Right Subtree Use Long bounds for edge cases!”

Backlinks