Validate Binary Search Tree

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
    }
    
    console.log("Checking ", node.val, lower, upper);
    
    // 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 algorithm works by checking the tree from top to bottom, validating each node against dynamically updated bounds. At each node, we verify two critical properties:

  1. Local validity: Does this node satisfy the BST property relative to its immediate parent?
  2. Subtree validity: Are both left and right subtrees valid BSTs with appropriate bounds?

The beauty of this approach is that it fails fast—as soon as we encounter a violation, we can immediately return false without checking the rest of the tree. Conversely, if we traverse the entire tree without finding violations, we know it’s a valid BST.

Why Recursion Works Here #

Recursion is ideal for tree problems because trees themselves are recursive data structures. Each node is the root of its own subtree, and the same validation logic applies at every level. By passing bounds down through recursive calls, we maintain the context needed to validate nodes deep in the tree against constraints established by their ancestors.

Code Breakdown #

Let’s examine each component of the solution in detail.

Main Function #

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

This wrapper function initiates the validation process by calling our helper function checkNode. Using a helper function is a common pattern in recursive tree algorithms for several reasons:

  • Parameter flexibility: The problem’s function signature may not include all the parameters we need for our algorithm
  • Clean interface: We can hide implementation details from the caller
  • Initial setup: We can establish initial conditions (like setting bounds to null) before entering the recursion

In this case, we start with null bounds because the root node has no constraints—it can be any value. As we traverse down the tree, these bounds will be updated based on the values we encounter.

Base Case: Terminal Condition #

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

This is the recursion’s base case, which prevents infinite recursion and handles leaf nodes properly. When we reach a null node (either an empty tree or beyond a leaf node), we return true because:

  • An empty tree is trivially a valid BST
  • Reaching a null child of a leaf node means we’ve successfully validated that entire path

This is crucial: we only return false when we find a violation. The absence of a node is not a violation, so we return true to allow the recursion to continue checking other paths.

Boundary Validation #

// 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;
}

This is where we perform the actual validation. These checks enforce the BST property by ensuring the current node’s value falls within the valid range established by its ancestors.

Understanding the Logic:

The lower bound represents the minimum value this node must exceed. This bound comes from ancestors on the right-child path—if we took a right turn to get here, all nodes below must be greater than that ancestor.

The upper bound represents the maximum value this node must be less than. This bound comes from ancestors on the left-child path—if we took a left turn to get here, all nodes below must be less than that ancestor.

JavaScript-Specific Note: The check lower != null before node.val <= lower is essential because JavaScript uses short-circuit evaluation. If lower is null, JavaScript won’t evaluate the second part of the && expression, preventing errors from comparing against null. This is a defensive programming practice that ensures our code handles edge cases gracefully.

Why <= and >= instead of < and >? Binary search trees typically don’t allow duplicate values. Using <= and >= ensures that if we encounter a value equal to a bound, we correctly identify it as a violation.

Recursive Validation #

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

Here’s where the magic of recursion happens. We recursively validate both subtrees, but with updated bounds:

Left Subtree Validation:

  • Lower bound: We pass along the existing lower bound unchanged because nodes in the left subtree must still be greater than any ancestor where we turned right
  • Upper bound: We pass node.val as the new upper bound because all nodes in the left subtree must be less than the current node

Right Subtree Validation:

  • Lower bound: We pass node.val as the new lower bound because all nodes in the right subtree must be greater than the current node
  • Upper bound: We pass along the existing upper bound unchanged because nodes in the right subtree must still be less than any ancestor where we turned left

This bound-passing mechanism is what allows us to enforce the global BST property—not just comparing children to parents, but ensuring every node in a subtree satisfies constraints from all relevant ancestors.

Success Case #

return true;

If we reach this line, it means:

  1. The current node’s value is within valid bounds
  2. The left subtree is a valid BST
  3. The right subtree is a valid BST

Therefore, the subtree rooted at this node is a valid BST, and we return true. This return value propagates up the call stack, eventually determining whether the entire tree is valid.

Complexity Analysis #

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

Space Complexity: O(h) where h is the height of the tree. This space is used by the recursion call stack. In the worst case (a skewed tree), h = n, making space complexity O(n). In a balanced tree, h = log(n), making space complexity O(log n).

Alternative Approaches #

While this solution is elegant and efficient, there are other ways to validate a BST:

  1. In-order Traversal: Perform an in-order traversal and check if the resulting sequence is strictly increasing
  2. Iterative with Stack: Convert the recursive solution to an iterative one using an explicit stack
  3. Min-Max Tracking: Similar to our approach but tracking actual min/max values instead of bounds

The recursive bound-checking approach we’ve explored is generally preferred because it’s intuitive, concise, and efficient both in time and space.

Previous Top K Frequent Elements