Binary Search Trees - Comprehensive Study Guide

🎯 Introduction to Binary Search Trees

What is a Binary Search Tree (BST)?

A BST is a binary tree in symmetric order. This means:

Each node contains a key and an associated value
Every node's key is larger than all keys in its left subtree
Every node's key is smaller than all keys in its right subtree

Binary Tree Structure

A binary tree is either:

Empty (null)
A node with references to two disjoint binary trees (left and right subtrees)

BST Anatomy

E (root) / \ / \ A S \ / \ C R X / \ H \ M

Note: Keys smaller than E are on the left, keys larger than E are on the right

🏗️ BST Fundamentals

Node Structure

private class Node {
    private Key key;           // sorted by key
    private Value val;         // associated value
    private Node left, right;  // left and right subtrees
    
    public Node(Key key, Value val) {
        this.key = key;
        this.val = val;
    }
}
                

⚠️ Key Requirements

The Key type must implement Comparable interface for ordering operations.

Keys must be unique and support comparison operations.

BST Properties

Property	Description
Symmetric Order	Left subtree < Node < Right subtree
Root	Top node of the tree
Leaf	Node with no children (both links null)
Parent	Node that has a link to another node
Depth	Number of links from root to node
Height	Maximum depth of any node

⚙️ BST Operations

1. Search Operation

Search Algorithm

Rule: If less, go left; if greater, go right; if equal, search hit!

public Value get(Key key) {
    Node x = root;
    while (x != null) {
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x = x.left;   // go left
        else if (cmp > 0) x = x.right;  // go right
        else              return x.val;   // found!
    }
    return null;  // not found
}
                

✅ Search Complexity

Cost: Number of compares = 1 + depth of node

Best case: O(log n) for balanced tree

Worst case: O(n) for degenerate tree

2. Insert Operation

Insert Algorithm

Rule: If less, go left; if greater, go right; if null, insert!

public void put(Key key, Value val) {
    root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val);  // insert here
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = put(x.left,  key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else              x.val   = val;  // update value
    
    return x;  // reset links on recursive path
}
                

Insert Example: Adding G to a BST

Before: After: S S / \ / \ E X E X / \ / \ A R A R \ / \ H H \ \ M M / G ← NEW

Start at root S (G < S, go left)
Compare with E (G > E, go right)
Compare with R (G < R, go left)
Compare with H (G < H, go left)
H.left is null → Insert G here!

3. Finding Minimum/Maximum

// Minimum: go left until reaching null
private Node min(Node x) {
    if (x.left == null) return x;
    return min(x.left);
}

// Maximum: go right until reaching null
private Node max(Node x) {
    if (x.right == null) return x;
    return max(x.right);
}
                

🗑️ BST Deletion (Hibbard Deletion)

⚠️ Deletion Complexity

Deletion is the most complex operation in BSTs. There are three cases to handle.

Case 0: No Children (Leaf Node)

Solution: Simply delete the node by setting the parent link to null.

Delete C: E E / \ / \ A S → A S \ C (DELETE) (removed)

Case 1: One Child

Solution: Replace the node with its child (bypass the node).

Delete R: E E / \ / \ A S → A S / \ / \ R X H X \ \ H M \ M

Case 2: Two Children (Most Complex)

Hibbard Deletion Algorithm

Find the node t to delete
Find successor x = minimum node in t's right subtree
Delete the minimum in t's right subtree
Replace t with x:
- Set x.left = t.left
- Set x.right = deleteMin(t.right)

Example: Deleting E (has 2 children)

Step 1: Find successor (min of right subtree) E ← DELETE Successor = H (min in right subtree) / \ A S / \ / \ C H R X \ M Step 2: Delete minimum from right subtree E / \ A S / / \ C R X \ M Step 3: Replace E with H H ← NEW ROOT / \ A S / / \ C R X \ M

Delete Minimum Helper Function

private Node deleteMin(Node x) {
    if (x.left == null) return x.right;  // replace with right child
    x.left = deleteMin(x.left);  // recurse left
    x.count = 1 + size(x.left) + size(x.right);  // update count
    return x;
}
                

Complete Delete Implementation

public void delete(Key key) {
    root = delete(root, key);
}

private Node delete(Node x, Key key) {
    if (x == null) return null;
    
    int cmp = key.compareTo(x.key);
    if      (cmp < 0) x.left  = delete(x.left,  key);
    else if (cmp > 0) x.right = delete(x.right, key);
    else {  // found node to delete
        // Case 0 & 1: no right child or no left child
        if (x.right == null) return x.left;
        if (x.left  == null) return x.right;
        
        // Case 2: two children - use Hibbard deletion
        Node t = x;
        x = min(t.right);              // find successor
        x.right = deleteMin(t.right);  // delete successor from right
        x.left = t.left;               // attach left subtree
    }
    x.count = size(x.left) + size(x.right) + 1;
    return x;
}
                

⚠️ Hibbard Deletion Problem

Unsatisfactory solution: Not symmetric!

Consequence: Trees become unbalanced after many deletions

Performance degradation: √N per operation (instead of log N)

Open problem: Simple and efficient delete for BSTs remains unsolved!

Lazy Deletion Alternative

Tombstone Approach

Set the node's value to null
Leave key in tree to guide searches
Don't consider it equal during search

Problem: Memory overhead increases over time (tombstone overload)

Cost: ~2 ln N' where N' = total keys ever inserted

📊 Performance Analysis

Tree Shape Matters!

Best Case (Balanced): Typical Case: Worst Case (Degenerate): H S A / \ / \ \ C S E X C / \ / \ / \ \ A E R X A R E \ \ \ C H H \ \ M M \ Height: log N log N Height: N R O(log n) O(log n) O(n) \ S \ X

Mathematical Analysis

Random Insertion (Average Case)

Proposition: If N distinct keys are inserted in random order:

Expected number of compares: ~2 ln N ≈ 1.39 log₂ N
Expected tree height: ~4.311 ln N (Reed, 2003)

Proof: 1-1 correspondence with quicksort partitioning

Worst Case

Height: N - 1 (linked list)
Occurs when keys inserted in sorted order
Probability: Exponentially small for random insertions

Complexity Summary Table

Operation	Best Case	Average Case	Worst Case
Search	log N	1.39 log N	N
Insert	log N	1.39 log N	N
Delete	log N	√N	N
Min/Max	log N	1.39 log N	N

⚠️ Delete Performance Degradation

After many deletions using Hibbard deletion, trees become unbalanced!

All operations degrade to √N on average

💻 Complete BST Implementation

Class Structure

public class BST<Key extends Comparable<Key>, Value> {
    private Node root;  // root of BST
    
    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int count;  // number of nodes in subtree
        
        public Node(Key key, Value val) {
            this.key = key;
            this.val = val;
            this.count = 1;
        }
    }
    
    public void put(Key key, Value val) { /* see above */ }
    public Value get(Key key) { /* see above */ }
    public void delete(Key key) { /* see above */ }
    public Iterable<Key> iterator() { /* inorder traversal */ }
}
                

Additional Useful Methods

// Size: number of nodes in tree
public int size() {
    return size(root);
}

private int size(Node x) {
    if (x == null) return 0;
    return x.count;
}

// Height: maximum depth
public int height() {
    return height(root);
}

private int height(Node x) {
    if (x == null) return -1;
    return 1 + Math.max(height(x.left), height(x.right));
}

// Floor: largest key ≤ given key
public Key floor(Key key) {
    Node x = floor(root, key);
    if (x == null) return null;
    return x.key;
}

private Node floor(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp == 0) return x;
    if (cmp < 0) return floor(x.left, key);
    Node t = floor(x.right, key);
    if (t != null) return t;
    else return x;
}
                

Tree Traversals

// Inorder: Left → Node → Right (gives sorted order!)
private void inorder(Node x) {
    if (x == null) return;
    inorder(x.left);
    System.out.println(x.key);
    inorder(x.right);
}

// Preorder: Node → Left → Right
private void preorder(Node x) {
    if (x == null) return;
    System.out.println(x.key);
    preorder(x.left);
    preorder(x.right);
}

// Postorder: Left → Right → Node
private void postorder(Node x) {
    if (x == null) return;
    postorder(x.left);
    postorder(x.right);
    System.out.println(x.key);
}
                

💡 Traversal Tip

Inorder traversal of a BST produces keys in sorted order!

This is why it's called "symmetric order" - the inorder traversal respects the ordering.

📝 Summary & Comparison

Symbol Table Implementation Comparison

Implementation	Search (Worst)	Insert (Worst)	Delete (Worst)	Search (Avg)	Insert (Avg)	Delete (Avg)	Ordered?
Sequential Search (Unordered List)	N	N	N	N/2	N	N/2	❌
Binary Search (Ordered Array)	log N	N	N	log N	N/2	N/2	✅
BST	N	N	N	1.39 log N	1.39 log N	√N	✅

Key Takeaways

✅ BST Advantages

Efficient search and insert: O(log N) on average
Supports ordered operations (min, max, floor, ceiling, rank)
Inorder traversal gives sorted order
Dynamic structure (no need to specify size upfront)
Simple recursive implementation

⚠️ BST Limitations

No performance guarantee: can degenerate to O(N)
Shape depends on insertion order
Delete operation degrades performance to √N
Not suitable when guaranteed performance is required

🚀 What's Next?

Balanced BSTs solve the performance guarantee problem!

2-3 Trees: Guaranteed log N performance
Red-Black Trees: Practical implementation of balanced BSTs
AVL Trees: Strictly balanced trees
B-Trees: For disk-based storage

Next lecture will cover how to guarantee logarithmic performance for all operations!

Quick Reference Card

BST Operations Cheat Sheet

Operation	Algorithm	Complexity (Avg)
Search	Compare, go left/right, repeat	O(log N)
Insert	Search, insert at null link	O(log N)
Delete (0 children)	Set parent link to null	O(log N)
Delete (1 child)	Replace with child	O(log N)
Delete (2 children)	Replace with successor (Hibbard)	O(√N)
Min/Max	Go all left/right	O(log N)
Floor/Ceiling	Search with fallback logic	O(log N)

Study Tips

📚 How to Master BSTs

Draw trees! Practice drawing insertion and deletion by hand
Trace algorithms: Follow the recursive calls step by step
Compare cases: Best vs average vs worst - understand when each occurs
Implement from scratch: Code it without looking at notes
Analyze complexity: Always count comparisons and consider tree height

Common Exam Questions

🎓 Practice Problems

Draw the BST resulting from inserting keys in order: 5, 2, 8, 1, 3, 7, 9
Show step-by-step deletion of a node with 2 children
What is the worst-case height of a BST with N nodes?
Why does Hibbard deletion degrade performance?
Compare BST vs Binary Search on arrays - when to use each?
Write recursive code for BST traversals (inorder, preorder, postorder)