Binary Tree BST Validation

The Full Definition of a BST

Let's quickly refresh the strict rules for a valid Binary Search Tree (BST):

• For any given node N:
  • All values in its entire left subtree must be less than N.val.
  • All values in its entire right subtree must be greater than N.val.
• Both the left and right subtrees must also be binary search trees.
• There are no duplicate values (this is a common convention).

The key words here are entire subtree. This is where many simple validation attempts fail.

The Common Pitfall: Local vs. Global Properties

A common first thought is to traverse the tree and, for each node, check if its left child is smaller and its right child is larger.

if node.left.val < node.val and node.right.val > node.val:

This check is insufficient. A node must be greater than all nodes in its left subtree, not just its direct child.

Consider this tree:

The value 4 in the right subtree violates the rule that all nodes in the right subtree of 5 must be greater than 5. A simple local check would miss this.

To understand this pitfall visually, watch the first few minutes of the following video.

The Correct Approach: Validating with Boundaries

To correctly validate a BST, we need to ensure that each node's value falls within a valid range, or boundary, defined by its ancestors. We can do this with a recursive traversal (like a pre-order traversal or DFS).

The logic is as follows:

1. We start at the root. The root can have any value, so its valid range is from negative infinity to positive infinity (-∞, +∞).
2. When we traverse to a left child, we know its value must be less than its parent. So, we tighten the valid range for the entire left subtree: the upper bound becomes the parent's value. The new range is (parent's lower_bound, parent's value).
3. When we traverse to a right child, we know its value must be greater than its parent. So, we tighten the valid range for the entire right subtree: the lower bound becomes the parent's value. The new range is (parent's value, parent's upper_bound).
4. At each node, we check if its value is within the (lower_bound, upper_bound) range passed down to it. If not, the tree is invalid. If we traverse the entire tree without any violations, it is a valid BST.

This image provides a great visualization of how the low and high boundaries are updated during the traversal.

Let's watch this boundary-passing technique in action.

Implementation with Recursive DFS

This algorithm is naturally implemented using a recursive helper function. The main function initiates the call with the root and infinite boundaries, and the helper function performs the traversal and validation.

For a clear, well-structured guide on implementing this, let's turn to CodePath's guide, which is designed with a problem-solving mindset similar to competitive programming.

Here's the Python implementation from the guide, which you should now be able to understand fully. Note the use of math.inf for the initial boundaries.

import math

# Assume we have a TreeNode class defined like this:
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # Helper function processes the tree with min and max boundaries.
        def helper(node: TreeNode, min_val: float, max_val: float) -> bool:
            # An empty node or subtree is a valid BST.
            if not node:
                return True
            
            # Check if the node's value is outside its valid range.
            # Note: A valid BST typically doesn't allow equal values.
            if not (min_val < node.val < max_val):
                return False
            
            # Recursively check the left and right subtrees with updated boundaries.
            # The 'and' ensures both subtrees must be valid.
            return (helper(node.left, min_val, node.val) and
                    helper(node.right, node.val, max_val))

        # Initial call for the root node with infinite boundaries.
        return helper(root, -math.inf, math.inf)

An Alternative Method: In-Order Traversal

There's another elegant way to solve this problem that leverages a key property you've already used: an in-order traversal of a valid BST visits nodes in ascending sorted order.

Therefore, we can validate a tree by:

1. Performing an in-order traversal.
2. Checking if the sequence of visited nodes is strictly increasing.

A naive way is to store all node values in a list during the traversal and then check if the list is sorted. However, this uses O(N) extra space for the list.

A more optimized approach avoids storing the whole list. During the in-order traversal, you can simply keep track of the value of the previously visited node. If the current node's value is not strictly greater than the previous node's value, you've found a violation.

Complexity Analysis

For competitive programming, analyzing the efficiency of your solution is critical.

• Time Complexity: Both the boundary-checking method and the in-order traversal method visit each node exactly once. Therefore, the time complexity for both is O(N), where N is the number of nodes in the tree.
• Space Complexity:
  • Boundary-Checking Method: The space is determined by the depth of the recursion stack. In a balanced tree, this is O(log N). In the worst case of a completely skewed tree (like a linked list), it is O(N).
  • In-Order Traversal Method: If you store the nodes in a list, the space complexity is O(N). For the optimized approach that only tracks the previous value, the space complexity is determined by the recursion stack, making it the same as the boundary-checking method: O(N) in the worst case.

Conclusion

In this lesson, you learned how to rigorously validate a binary tree to see if it conforms to the BST properties. This is a fundamental skill that reinforces your understanding of both BSTs and tree traversal algorithms.

Key Takeaways:

• Validating a BST requires checking global properties, not just the local relationship between a parent and its immediate children.
• The boundary-checking (or range-checking) method is a robust way to validate a BST. It uses a recursive function that passes down a (min_val, max_val) range for each node.
• An alternative approach is to use an in-order traversal and verify that the nodes are visited in strictly ascending order.
• Both primary methods have a time complexity of O(N) and a worst-case space complexity of O(N) due to the recursion stack.

Up Next:
We've just seen how powerful in-order traversal is for validation. In the next lesson, we will formalize our knowledge of tree traversals and focus on performing an in-order traversal on a BST to retrieve elements in sorted order. We'll also explore its iterative implementation using a stack, a crucial technique in competitive programming to avoid recursion depth limits and manage memory more explicitly.