Module 6.2 ⏱ 45 min read ⚡ Binary Search Trees & Validations

Binary Search Trees (BST)

Master BST invariants, searching, insertion/deletion mechanics, node validation, and Lowest Common Ancestor optimization strategies.

1. BST Invariants & Core Operations

A Binary Search Tree (BST) is a specialized binary tree ordered according to the BST invariant: for any given node, all keys in its left subtree are strictly less than the node's key, and all keys in its right subtree are strictly greater than the node's key.

Core Operations: Searching, inserting, and deleting nodes take $O(h)$ time, where $h$ is the height of the tree. In a balanced BST, this translates to $O(\log n)$ efficiency. Deletion requires handling three cases: nodes with no children, nodes with a single child, and nodes with two children (by finding the in-order successor or predecessor).

2. Validating BSTs & Lowest Common Ancestor (LCA)

Validation: Simply checking if a node's left child is smaller and its right child is larger is insufficient. Every node must fall within a valid dynamic range `(min_val, max_val)` passed down recursively through the tree.

Lowest Common Ancestor (LCA): In a BST, the LCA of two nodes $p$ and $q$ can be found efficiently without extra traversal. If both $p$ and $q$ are smaller than the root, the LCA lies in the left subtree. If both are greater, it lies in the right subtree. The first node where $p$ and $q$ diverge is our LCA.

// C++ Solution: Lowest Common Ancestor of a BST
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while (root) {
            if (p->val < root->val && q->val < root->val) {
                root = root->left;
            } else if (p->val > root->val && q->val > root->val) {
                root = root->right;
            } else {
                return root;
            }
        }
        return nullptr;
    }
};
            

# Python Solution: Lowest Common Ancestor of a BST
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        while root:
            if p.val < root.val and q.val < root.val:
                root = root.left
            elif p.val > root.val and q.val > root.val:
                root = root.right
            else:
                return root
        return None
            

// Java Solution: Lowest Common Ancestor of a BST
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }
}
            

3. Homework & Quiz Overview

To lock in your mastery, complete the implementation exercises for Validating a BST and finding the Lowest Common Ancestor in a BST.

Quick Check: Test Your Intuition

Why is checking only the immediate left and right child insufficient when validating a Binary Search Tree?