Validate Binary Search Tree

The problem

Given a binary tree, determine if it is a valid BST: for every node, all left descendants < node and all right descendants > node (classic LC: strict).

    2
   / \
  1   3   → true

    5
   / \
  1   4
     / \
    3   6   → false (3 is in right subtree of 5 but 3 < 5)

Brute wrong approach

Only check left.val < root.val < right.val for immediate children — fails on the second example.

Optimal A: range recursion

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

Using ±Infinity also works if values fit safely in JS numbers.

Optimal B: inorder increasing

Inorder of a BST is sorted. Track previous value.

function isValidBSTInorder(root: TreeNode | null): boolean {
  let prev: number | null = null;
  function dfs(node: TreeNode | null): boolean {
    if (!node) return true;
    if (!dfs(node.left)) return false;
    if (prev !== null && node.val <= prev) return false;
    prev = node.val;
    return dfs(node.right);
  }
  return dfs(root);
}

Time	O(n)
Space	O(h)

Edge cases

• Empty / single node → true
• Duplicates — usually invalid for strict BST
• INT_MIN / INT_MAX values — prefer null bounds over ±Infinity if values can be those
• Left child valid locally but breaks ancestor bound

Common bugs

• Local-only child checks
• <= vs < inconsistency
• Reusing Infinity when node.val can equal Infinity

Interview delivery

1. Full BST property, not local.
2. Bounds DFS or inorder.
3. Trace the classic false case.
4. O(n).
5. Follow-up: recover BST / kth small.

Related

• Lowest Common Ancestor BST
• Kth Smallest in BST
• Same Tree
• Binary Tree Level Order

The classic trap tree

      5
     / \
    1   4
       / \
      3   6

Node 3 is left of 4 (locally ok) but sits in the right subtree of 5, so it must be > 5. Bounds method catches this: when going right from 5, low=5; 3 ≤ 5 fails.

Duplicates policy

LeetCode 98: equal values are invalid. Use <= / >= rejections. Some textbooks allow left ≤. Confirm.

Inorder iterative

You can use an explicit stack for inorder and compare to prev — avoids recursion depth issues on skewed trees. Same O(n)/O(h).

Further reading

• LeetCode 98 — Validate Binary Search Tree
• Binary search tree