5.2 Validate Binary Search Tree

5.2.1 Problem Metadata

5.2.2 Description

Check whether a binary tree is a valid BST.

5.2.3 Examples

Example 1: Valid BST

Input:
    2
   / \
  1   3
Output: true
Explanation: All left values (1) are less than root (2), all right values (3) are greater

Example 2: Invalid BST

Input:
    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: Node 4's left child (3) violates the BST property for subtree rooted at 5

Example 3: Single Node

Input: 1
Output: true
Explanation: A single node is always a valid BST

5.2.4 Constraints

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

5.2.5 Solution - Inorder Bounds

5.2.5.1 Walkthrough

Perform DFS carrying the valid range for each subtree:

  1. Start with no bounds at root.
  2. For a node, if its value is not strictly within (low, high), return false.
  3. Recurse left with updated high = node.val (all left nodes must be smaller).
  4. Recurse right with updated low = node.val (all right nodes must be larger).
  5. Return true only if both subtrees are valid.

Passing bounds prevents false positives that would slip through a simple local child comparison.

5.2.5.2 Analysis

  • Time Complexity: O(n) — visit each node once
  • Space Complexity: O(h) recursion stack (h = tree height)

5.2.5.3 Code - Java

public boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}

private boolean validate(TreeNode node, Integer low, Integer high) {
    if (node == null) {
        return true;
    }
    if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
        return false;
    }
    return validate(node.left, low, node.val) && validate(node.right, node.val, high);
}

5.2.5.4 Code - Golang

func isValidBST(root *TreeNode) bool {
    return validate(root, math.MinInt32 - 1, math.MaxInt32 + 1)
}

func validate(node *TreeNode, low int, high int) bool {
    if node == nil {
        return true;
    }

    if node.Val <= low || node.Val >= high {
        return false;
    }

    return validate(node.Left, low, node.Val) && validate(node.Right, node.Val, high);
}