medium Validate Binary Search Tree

Problem Statement

Determine if a given binary tree is a binary search tree (BST). In a BST, for each node:

• All nodes to its left have values less than the node's value.
• All nodes to its right have values greater than the node's value.

Examples

Example 1:

• Input: [5,3,7]
• Expected Output: true
• Justification: The left child of the root (3) is less than the root, and the right child of the root (7) is greater than the root. Hence, it's a BST.

Example 2:

• Input: [5,7,3]
• Expected Output: false
• Justification: The left child of the root (7) is greater than the root, making it invalid.

Example 3:

• Input: [10,5,15,null,null,12,20]
• Expected Output: true
• Justification: Each subtree of the binary tree is a valid binary search tree, so the whole binary tree is a valid binary search tree.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁴].
• -2^31 <= Node.val <= 2^31 - 1

Solution

To validate a binary search tree, we use a recursive range check. Every node must be strictly greater than every node in its left subtree and strictly smaller than every node in its right subtree. Instead of comparing only with immediate children, we pass down an allowed interval (min, max) from the node's ancestors.

Why the naive parent-vs-child check is wrong. The classic bug is to check only that node.left.val < node.val < node.right.val at each node. That enforces the invariant locally but not globally. Counterexample: [5,4,6,null,null,3,7] — root 5 with left 4 and right 6, and 6 has children 3 and 7. Every parent/child pair passes (4<5, 6>5, 3<6, 7>6), yet the tree is not a BST: node 3 lives in 5's right subtree, so it must be > 5, but 3 < 5. A single ancestor comparison misses this; the running (min, max) interval catches it because 3 is checked against (5, 6) and fails 3 > 5. The interval is what carries every ancestor's constraint down, not just the immediate parent's.

Alternative — inorder traversal. Because an inorder walk of a valid BST yields values in strictly ascending order, you can instead traverse inorder while tracking the previous value and assert each node is strictly greater than its predecessor. Same O(n) time; pick it when you are already writing a traversal, or the range method when you want to short-circuit as early as possible on the first violation.

1. Base case: A null node is a valid BST.
2. Check the current node: Its value must satisfy min < node.val < max. If not, return false.
3. Recurse left: The left child keeps the same min but uses node.val as the new max.
4. Recurse right: The right child keeps the same max but uses node.val as the new min.
5. Return the logical AND of both recursive calls.

We use long bounds initialized to Long.MIN_VALUE and Long.MAX_VALUE so that a node value equal to Integer.MIN_VALUE or Integer.MAX_VALUE is still accepted.

Algorithm Walkthrough

For the tree [10,5,15,null,null,12,20]:

• Root 10 is checked against (-∞, +∞) and is valid.
• Left child 5 is checked against (-∞, 10) and is valid.
• Right child 15 is checked against (10, +∞) and is valid.
• Left child of 15 is 12, checked against (10, 15) and is valid.
• Right child of 15 is 20, checked against (15, +∞) and is valid.
• All subtrees are valid, so the tree is a BST.

Code

// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  // Main method to check if a tree is a BST
  public boolean isValidBST(TreeNode root) {
    // Initially, the range is set to the largest and smallest possible values
    return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
  }

  // Helper method that checks the node value against a range
  private boolean isValidBSTHelper(TreeNode node, long min, long max) {
    // Null nodes are always BST
    if (node == null) return true;

    // Node value should be strictly within the min and max
    if (node.val <= min || node.val >= max) return false;

    // Recursively check left (with updated max) and right (with updated min)
    return (
      isValidBSTHelper(node.left, min, node.val) &&
      isValidBSTHelper(node.right, node.val, max)
    );
  }

  // Test the solution with the examples
  public static void main(String[] args) {
    Solution sol = new Solution();

    TreeNode example1 = new TreeNode(5);
    example1.left = new TreeNode(3);
    example1.right = new TreeNode(7);
    System.out.println(sol.isValidBST(example1)); // true

    TreeNode example2 = new TreeNode(5);
    example2.left = new TreeNode(7);
    example2.right = new TreeNode(3);
    System.out.println(sol.isValidBST(example2)); // false

    TreeNode example3 = new TreeNode(10);
    example3.left = new TreeNode(5);
    example3.right = new TreeNode(15);
    example3.right.left = new TreeNode(12);
    example3.right.right = new TreeNode(20);
    System.out.println(sol.isValidBST(example3)); // true
  }
}

Time Complexity

O(n) — we visit each node exactly once.

Space Complexity

O(h) — the recursion stack depth equals the tree height. In the worst case (a completely skewed tree) it is O(n); for a balanced tree it is O(log n).

Try it yourself

Try solving this question on LeetCode.

---

Problem and solution structure adapted from DesignGurus. Re-authored and corrected for this guide.

I'm working on the problem **Validate Binary Search Tree** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Validate Binary Search Tree** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Validate Binary Search Tree**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Validate Binary Search Tree**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.