Validate Binary Search Tree

Problem Statement #

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

A BST is defined as follows:

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

Solution #

var isValidBST = function(root) {
    return checkNode(root, null, null);
};

// Helper function for recursion
function checkNode(node, lower, upper) {
    // All nodes to left of node should be less than this node value
    // All nodes to right of node should be more than this node value

    if (!node) {
        return true; // Empty so at end of path
    }

    // Check both sides
    if (lower != null && node.val <= lower) { // This node below the limit
        return false;
    }
    if (upper != null && node.val >= upper) { // This node above the limit
        return false;
    }
    if (!checkNode(node.left, lower, node.val)) {
        return false;
    }
    if (!checkNode(node.right, node.val, upper)) {
        return false;
    }
    return true;
}

Approach and Strategy #

This is a classic tree validation problem that demonstrates the power of recursive thinking. The key insight lies in the third condition of what defines a binary search tree: “Both the left and right subtrees must also be binary search trees.” This recursive definition naturally suggests a recursive solution.

The Subtle Challenge #

Many developers initially approach this problem with a simple check: “Is the left child less than the parent, and is the right child greater than the parent?” While this seems logical, it misses a crucial requirement.

Consider this tree:

    5
   / \
  1   6
     / \
    4   7

A naive check would validate each parent-child relationship:

  • 5’s left child (1) is less than 5 ✓
  • 5’s right child (6) is greater than 5 ✓
  • 6’s left child (4) is less than 6 ✓
  • 6’s right child (7) is greater than 6 ✓

But this tree is NOT a valid BST! Why? Because node 4 is in the right subtree of node 5, which means it must be greater than 5. However, 4 < 5, violating the BST property.

The Correct Approach: Range Validation #

The solution requires tracking not just the parent value, but the valid range of values for each node. As we traverse the tree, we maintain lower and upper bounds that constrain what values are acceptable at each position.

Key insight: Every node has an acceptable range of values determined by its ancestors in the tree, not just its immediate parent.

Algorithm Explanation #

Function Signature #

function checkNode(node, lower, upper)

Parameters:

  • node: The current node we’re validating
  • lower: The lower bound (exclusive) - this node’s value must be greater than this
  • upper: The upper bound (exclusive) - this node’s value must be less than this

Returns: true if the subtree rooted at node is a valid BST, false otherwise

Base Case #

if (!node) {
    return true;
}

An empty node (null) is considered valid. This makes sense because an empty subtree doesn’t violate any BST properties. This also serves as our recursion termination condition.

Bound Validation #

if (lower != null && node.val <= lower) {
    return false;
}
if (upper != null && node.val >= upper) {
    return false;
}

We check if the current node’s value falls within the acceptable range:

  • If a lower bound exists and the node’s value is not greater than it, fail
  • If an upper bound exists and the node’s value is not less than it, fail

Note: We check for != null because bounds can legitimately be negative numbers or zero. We can’t use truthiness checks here.

Recursive Validation #

if (!checkNode(node.left, lower, node.val)) {
    return false;
}
if (!checkNode(node.right, node.val, upper)) {
    return false;
}

This is where the magic happens:

For the left subtree:

  • The lower bound stays the same (inherited from parent)
  • The upper bound becomes the current node’s value
  • This ensures all nodes in the left subtree are less than the current node

For the right subtree:

  • The lower bound becomes the current node’s value
  • The upper bound stays the same (inherited from parent)
  • This ensures all nodes in the right subtree are greater than the current node

Success Case #

return true;

If we’ve validated the current node and both subtrees without finding violations, this subtree is a valid BST.

Example Walkthrough #

Let’s trace through the invalid tree example:

    5
   / \
  1   6
     / \
    4   7

Call sequence:

  1. checkNode(5, null, null) - Root node, no bounds

    • 5 passes (no bounds to violate)
    • Checks left: checkNode(1, null, 5)

  2. checkNode(1, null, 5) - Left child of 5

    • 1 < 5, passes
    • Checks left: checkNode(null, null, 1) → returns true
    • Checks right: checkNode(null, 1, 5) → returns true
    • Returns true

  3. Back to root, checks right: checkNode(6, 5, null) - Right child of 5

    • 6 > 5, passes
    • Checks left: checkNode(4, 5, 6)

  4. checkNode(4, 5, 6) - This is where it fails!

    • 4 is not greater than lower bound 5
    • Returns false

The algorithm correctly identifies that 4 violates the BST property because it’s in the right subtree of 5 but is less than 5.

Time and Space Complexity #

Time Complexity: O(n) where n is the number of nodes. We visit each node exactly once.

Space Complexity: O(h) where h is the height of the tree. This represents the space used by the recursion call stack. In the worst case (a completely unbalanced tree), h = n, giving O(n) space. In the best case (a balanced tree), h = log(n), giving O(log n) space.

Key Takeaways #

  1. Local checks aren’t sufficient: You can’t just compare each node with its immediate children
  2. Propagate constraints: Track the valid range of values as you traverse the tree
  3. Recursion fits the problem: BST validation is naturally recursive because BSTs are defined recursively
  4. Handle nulls carefully: Use explicit null checks rather than truthiness when bounds can be any number
  5. Update bounds appropriately: Left children become new upper bounds, right children become new lower bounds

This problem teaches the important concept that tree properties often depend on relationships beyond immediate parent-child connections, requiring a more global view maintained through recursion parameters.

Previous Valid Anagram