Week 10: Binary Search Trees

1. BST Properties & Search

A binary search tree is a binary tree with one extra rule applied at every single node: every value in its left subtree is smaller than the node's own value, and every value in its right subtree is larger. This holds recursively — not just for a node's immediate children, but for every node in both subtrees — which is precisely what makes Week 9's inorder traversal produce values in sorted order on a BST.

That invariant is what makes search fast: at each node, comparing the target to the node's value tells you which entire subtree can be safely ignored, the same divide-and-conquer idea as binary search on a sorted array from Week 3:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* search(TreeNode* node, int target) {
    if (node == nullptr || node->val == target) return node;   // base cases
    return target < node->val ? search(node->left, target)
                               : search(node->right, target);
}

Each recursive call discards one entire subtree, so search costs O(h) where h is the tree's height — O(log n) when the tree is balanced, but degrading to O(n) on a skewed tree, exactly like the worst-case linked-list shape from Week 9.

2. Insertion & Deletion

Insertion follows the same left/right decision as search, except it stops at the first nullptr it finds and attaches a new node there instead of failing:

TreeNode* insert(TreeNode* node, int val) {
    if (node == nullptr) return new TreeNode(val);   // base case: found the insertion point
    if (val < node->val) node->left = insert(node->left, val);
    else if (val > node->val) node->right = insert(node->right, val);
    // val == node->val: duplicate -- ignored here; some problems store a count instead
    return node;
}

Deletion is the one BST operation genuinely worth memorizing carefully, because it has three distinct cases depending on how many children the node being removed has:

TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) return nullptr;              // key not found -- nothing to do

    if (key < root->val) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        root->right = deleteNode(root->right, key);
    } else {
        // Found the node to delete.
        if (root->left == nullptr) {                  // Case 1/2: zero or one (right) child
            TreeNode* right = root->right;
            delete root;
            return right;
        }
        if (root->right == nullptr) {                 // Case 2: exactly one (left) child
            TreeNode* left = root->left;
            delete root;
            return left;
        }
        // Case 3: two children -- replace with the inorder successor
        // (smallest value in the right subtree), then delete that successor.
        TreeNode* successor = findMin(root->right);
        root->val = successor->val;
        root->right = deleteNode(root->right, successor->val);
    }
    return root;
}

The two-children case is the subtle one: you can't just remove the node, because that would disconnect both of its subtrees. Instead you copy in a value that's guaranteed to preserve the ordering invariant — the smallest value in the right subtree (or equivalently, the largest in the left subtree) — and then recursively delete that value from its original position, which is now guaranteed to be a zero- or one-child case. Both insertion and deletion run in O(h) time.

3. Validating a BST

A common mistake is checking only that a node's value is greater than its left child and less than its right child. That's not sufficient — the BST property must hold against every node in each subtree, not just the immediate children. The correct approach threads a valid (lower, upper) range down through the recursion, tightening it at every step:

#include <climits>

bool isValidBST(TreeNode* node, long long lower, long long upper) {
    if (node == nullptr) return true;                 // base case: empty tree is valid
    if (node->val <= lower || node->val >= upper) return false;
    return isValidBST(node->left, lower, node->val) &&
           isValidBST(node->right, node->val, upper);
}

bool isValidBST(TreeNode* root) {
    return isValidBST(root, LLONG_MIN, LLONG_MAX);
}

As the recursion descends into the left subtree, the upper bound tightens to the parent's value; descending right tightens the lower bound instead — so a node deep in a left subtree is checked against every ancestor it needs to be smaller than, not just its immediate parent. long long bounds (rather than int) avoid overflow issues if node values sit near INT_MIN/INT_MAX.

An equally valid alternative reuses Week 9's inorder traversal directly: run inorder and check that the resulting sequence is strictly increasing — a direct consequence of inorder producing sorted output only when the BST property genuinely holds throughout.

4. Lowest Common Ancestor

The lowest common ancestor (LCA) of two nodes p and q is the deepest node that has both of them as descendants (a node counts as its own descendant). In a general binary tree this needs a full postorder-style search of both subtrees, but the BST invariant gives a huge shortcut: at any node, you can tell which direction to go just by comparing values, without exploring both sides:

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == nullptr) return nullptr;

    if (p->val < root->val && q->val < root->val)
        return lowestCommonAncestor(root->left, p, q);    // both smaller -- go left

    if (p->val > root->val && q->val > root->val)
        return lowestCommonAncestor(root->right, p, q);   // both larger -- go right

    return root;   // split point: p and q fall on different sides (or one equals root)
}

This runs in O(h) time and O(1) extra space if written iteratively as a while loop instead of recursively, since at most one recursive branch is ever taken. A general (non-BST) binary tree's LCA algorithm can't use value comparisons to prune a side away — it has to search both subtrees via postorder and combine the results, which costs O(n) instead.

5. Diameter-of-a-Tree Problems

The diameter of a binary tree is the number of edges on the longest path between any two nodes — and critically, that path does not need to pass through the root. A naive approach recomputes height from scratch at every node, costing O(n²) in the worst case. The efficient version computes height and updates a running diameter in the same postorder pass, using the same "combine child results into a parent result" shape you used for maxDepth in Week 9:

#include <algorithm>
using namespace std;

int diameter = 0;   // tracked across the whole traversal

int height(TreeNode* node) {
    if (node == nullptr) return 0;                 // base case
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);

    diameter = max(diameter, leftHeight + rightHeight);  // longest path THROUGH this node

    return 1 + max(leftHeight, rightHeight);        // height, for the caller (parent) to use
}

int diameterOfBinaryTree(TreeNode* root) {
    diameter = 0;
    height(root);
    return diameter;
}

Each node computes and returns its own height (needed by its parent), while separately updating a shared diameter variable with the best path that routes through it (leftHeight + rightHeight edges). Because every node is visited exactly once and does O(1) work beyond its recursive calls, this runs in O(n) time and O(h) space — a large improvement over the naive quadratic version, and the same "return one thing, but also update shared state along the way" pattern generalizes to many other "longest path" or "max sum path" tree problems.

6. Hands-on Exercise

7. Knowledge Check

Four quick questions. Expand each to check your answer.