LeetCode 98 — Validate Binary Search Tree

Problem Summary

You are given the root of a binary tree.
Your task is to determine whether the tree is a valid Binary Search Tree (BST).

A valid BST must satisfy:

The left subtree of a node contains only nodes with values less than the node’s value.
The right subtree contains only nodes with values greater than the node’s value.
Both subtrees must themselves be valid BSTs.

Example
Input:

    2
   / \
  1   3

Output: true

Input:

Output: false
Reason: The right subtree contains 3, which is not greater than 5.

Approach 1: Recursion Using Min/Max Boundaries (Most Common Solution)

This is the standard and most intuitive method.

Key Idea

For every node, you maintain a valid range of values:

A node’s value must be greater than all values in its left ancestors.
A node’s value must be less than all values in its right ancestors.

We track these rules using min and max boundaries passed down recursively.

Why This Works

A local check (node.left < node.val < node.right) is not enough.
We must ensure the entire subtree respects the bounds created by earlier ancestors.

The min/max technique enforces all global BST rules.

Steps

Start with the full range: (min = -∞, max = +∞).
For each node:
- If node.val is outside (min, max), return false.
- Recursively check:
  - Left child must be in (min, node.val)
  - Right child must be in (node.val, max)
If all nodes satisfy the constraints, return true.

Java Code (Min/Max Boundary Approach)

class Solution {

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

    private boolean validate(TreeNode node, long min, long max) {
        if (node == null) return true;

        if (node.val <= min || node.val >= max) {
            return false;
        }

        return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}

Notes:

long is used for boundaries to avoid integer overflow issues.
The check is strict (< and >), not <=, because duplicates are not allowed in a BST.

Approach 2: Inorder Traversal (Sorted Order Check)

A BST’s inorder traversal produces a strictly increasing sequence.

Key Idea

Perform inorder traversal.
If any value is less than or equal to the previous value, it is not a BST.

Why This Works

Inorder traversal of a BST always yields a strictly increasing sequence.
If the sequence is not increasing, the BST rules are violated.

Steps

Traverse the tree inorder.
Keep track of the previously visited value.
If current value ≤ previous value → not a BST.
If traversal finishes successfully → valid BST.

Java Code (Inorder Traversal Approach)

class Solution {

    private Long prev = null;

    public boolean isValidBST(TreeNode root) {
        return inorder(root);
    }

    private boolean inorder(TreeNode node) {
        if (node == null) return true;

        if (!inorder(node.left)) return false;

        if (prev != null && node.val <= prev) {
            return false;
        }
        prev = (long) node.val;

        return inorder(node.right);
    }
}

Dry Run (Min/Max Boundary Approach)

Consider the invalid BST:

Initial call: validate(5, -∞, +∞)

Step 1: Node = 5

Valid: -∞ < 5 < +∞
Left subtree range = (-∞, 5)
Right subtree range = (5, +∞)

Step 2: Check left subtree

Node = 1
Range = (-∞, 5)
Valid: -∞ < 1 < 5
Left and right are null → valid

Step 3: Check right subtree

Node = 4
Range = (5, +∞)
Check: 4 > 5? No → Invalid

Return false immediately.

Complexity Analysis

Min/Max Boundary Approach

Time: O(n)
Space: O(h) recursion depth, h = tree height

Inorder Approach

Time: O(n)
Space: O(h)

Both solutions are efficient and acceptable.

Edge Cases

Null tree (empty tree): valid BST
Single node: valid
Left child equal to parent: invalid
Right child less than parent but deep inside subtree: caught by min/max
Integer overflow: prevent using long boundaries