Validating a Binary Search Tree

1. The Obvious (and Incorrect) Approach

Let's start by defining the BST property again:

1. A node's left subtree contains only nodes with keys less than the node's key.
2. A node's right subtree contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

A first-instinct solution might be to traverse the tree and, for each node, check if its left child is smaller and its right child is larger.

// A tempting but FLAWED approach
boolean isBST(Node node) {
    if (node == null) return true;
    
    // Check local properties
    if (node.left != null && node.left.key >= node.key) return false;
    if (node.right != null && node.right.key <= node.key) return false;
    
    // Recurse on children
    return isBST(node.left) && isBST(node.right);
}

This seems logical, but it's wrong. Why? Because this check is only local. The BST property must be global. A node's value must be correct relative to all its ancestors, not just its immediate parent.

To see why this fails, let's watch a short segment of a video that provides a perfect example.

As the video showed, a node like 10 can be less than its parent 15, but because it's in the right subtree of 11, it violates the rule that all nodes in the right subtree must be greater than 11.

Now that we understand the problem's subtlety, let's explore two correct and efficient solutions.

2. Approach 1: Recursive Range Checking

The most robust way to solve this is to ensure each node's value falls within a valid range (min, max). We pass this range down during our traversal and tighten the constraints at each level.

Here's the logic:

• The root of the tree can be any value, so its initial range is (-∞, +∞).
• When we traverse to the left child of a node N with value v, we know all nodes in this subtree must be less than v. So, the new valid range for the left child becomes (min_from_parent, v).
• When we traverse to the right child of N, we know all nodes in this subtree must be greater than v. So, the new valid range becomes (v, max_from_parent).

If any node's value falls outside the (min, max) range it's supposed to be in, the tree is not a valid BST.

This video provides a concise walkthrough of this approach.

Here is how you would structure this in Java. Notice the use of a helper function, a common pattern in recursive tree problems.

// We use Long for the min/max range to handle cases where a node's value is
// Integer.MIN_VALUE or Integer.MAX_VALUE.
public boolean isValidBST(Node root) {
    return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValid(Node node, long min, long max) {
    // Base case: An empty tree is a valid BST.
    if (node == null) {
        return true;
    }

    // Check if the current node's value is within its valid range.
    if (node.key <= min || node.key >= max) {
        return false;
    }

    // Recursively check the subtrees with updated ranges.
    // For the left subtree, the new max is the current node's key.
    // For the right subtree, the new min is the current node's key.
    return isValid(node.left, min, node.key) && 
           isValid(node.right, node.key, max);
}

3. Approach 2: In-order Traversal

There's another clever approach that leverages a key property we've seen before: an in-order traversal of a valid BST visits the nodes in ascending sorted order.

This insight changes the problem: we can perform an in-order traversal and simply check if the sequence of node values is sorted.

While you could store the entire in-order traversal in a list and check it afterwards, that would require $O(N)$ extra space. A more optimized solution uses $O(H)$ space (for the recursion stack) by checking the order on the fly.

The logic is:

1. During the in-order traversal (left -> root -> right), keep track of the value of the previously visited node.
2. When you visit the current node, compare its value to the previous node's value.
3. If the current value is not strictly greater than the previous value, the tree is not a valid BST.
4. After visiting the current node, update the previous value to the current node's value before traversing the right subtree.

Let's read about this approach and see its implementation.

The optimized in-order approach is often considered more elegant, but it can be trickier to implement correctly in an interview, especially iteratively. Let's look at a recursive Java implementation. A simple way to handle the previous value across recursive calls is to use a member variable or a boxed integer wrapper.

public class Solution {
    // Using a boxed type so it can be null for the first node.
    private Integer prev = null;

    public boolean isValidBST(Node root) {
        return inorder(root);
    }

    private boolean inorder(Node node) {
        if (node == null) {
            return true;
        }

        // 1. Traverse left subtree
        if (!inorder(node.left)) {
            return false;
        }

        // 2. Visit current node
        // For the very first node, prev is null, so this check is skipped.
        // For all subsequent nodes, check if the order is maintained.
        if (prev != null && node.key <= prev) {
            return false;
        }
        // Update prev to the current node's key
        prev = node.key;

        // 3. Traverse right subtree
        return inorder(node.right);
    }
}

Note: In an interview, be careful with mutable state like the prev field if the Solution object is reused across multiple test cases. You would need to reset it before each top-level call.

4. Complexity Analysis

Both correct approaches are efficient. Let $N$ be the number of nodes and $H$ be the height of the tree.

• Range-Checking Method:

  • Time Complexity: $O(N)$. We visit every node exactly once.
  • Space Complexity: $O(H)$. This space is used by the recursion call stack. For a balanced tree, $H\approx \log N$. For a completely unbalanced (skewed) tree, $H=N$.

• In-order Traversal Method (Optimized):

  • Time Complexity: $O(N)$. We still visit every node once.
  • Space Complexity: $O(H)$. Similar to the range-checking method, the space is dominated by the recursion stack.

Both methods are excellent, and you should be prepared to explain and implement either one in an interview. The range-checking method is often considered slightly more direct and less prone to implementation errors with state management.

Conclusion

Fantastic work! You've now mastered a classic tree problem that moves beyond simple implementation to validation and logical reasoning. This is exactly the kind of problem you'll face in technical interviews.

Key Takeaways:

• Validating a BST requires a global property check, not just a local one between a parent and its immediate children.
• The recursive range-checking method is a robust solution that passes (min, max) bounds down the tree, ensuring every node fits its global constraints.
• The in-order traversal method provides an alternative solution by leveraging the property that an in-order traversal of a valid BST yields a sorted sequence. The space-optimized version checks this on the fly.
• Both optimal solutions have a time complexity of $O(N)$ and space complexity of $O(H)$.

Preview of the Next Lesson:
In both this and the previous lesson, we've hinted at the major weakness of a standard BST: its performance degrades to $O(N)$ if the tree becomes unbalanced. How do we prevent this? The solution is self-balancing trees. In our next lesson, we will explain the need for self-balancing trees and dive into our first example by performing AVL tree rotations.