Binary Search Trees

🌳 Binary Search Trees: Your Magical Library Adventure!

Imagine you have a HUGE library with thousands of books. How do you find the book you want quickly? You could check every single book… but that would take forever!

What if the library was organized in a special way where every time you look at a book, you instantly know whether to go LEFT or RIGHT to find what you need?

That’s exactly what a Binary Search Tree (BST) does! It’s like a super-organized library where finding anything is lightning fast! ⚡

🏠 BST Fundamentals: The Magic Library Rules

What Makes a BST Special?

Think of a BST like a family tree, but with one golden rule:

LEFT children are SMALLER. RIGHT children are BIGGER.

That’s it! This simple rule makes searching incredibly fast!

graph TD
    A["50 - Root Book"] --> B["30 - Smaller, go LEFT"]
    A --> C["70 - Bigger, go RIGHT"]
    B --> D["20"]
    B --> E["40"]
    C --> F["60"]
    C --> G["80"]

Simple Example: Finding Book #40

1. Start at root: 50
2. Is 40 < 50? YES! Go LEFT
3. Arrive at: 30
4. Is 40 > 30? YES! Go RIGHT
5. Found it: 40! 🎉

Only 3 steps instead of checking all 7 books!

Java Code: BST Node

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

🔧 BST Core Operations: The Librarian’s Tools

Every librarian needs three main skills:

1️⃣ SEARCH: Finding a Book

TreeNode search(TreeNode root, int key) {
    if (root == null || root.val == key)
        return root;

    if (key < root.val)
        return search(root.left, key);

    return search(root.right, key);
}

Think of it like this:

• “Is this the book?” → Found it!
• “Is my book smaller?” → Check left shelf
• “Is my book bigger?” → Check right shelf

2️⃣ INSERT: Adding a New Book

When a new book arrives, walk down the tree until you find an empty spot!

TreeNode insert(TreeNode root, int val) {
    if (root == null)
        return new TreeNode(val);

    if (val < root.val)
        root.left = insert(root.left, val);
    else if (val > root.val)
        root.right = insert(root.right, val);

    return root;
}

Example: Insert 35 into our tree:

1. 35 < 50 → Go LEFT to 30
2. 35 > 30 → Go RIGHT to 40
3. 35 < 40 → Go LEFT… empty! Place 35 here! ✅

3️⃣ DELETE: Removing a Book

This is trickier! Three cases:

TreeNode delete(TreeNode root, int key) {
    if (root == null) return null;

    if (key < root.val)
        root.left = delete(root.left, key);
    else if (key > root.val)
        root.right = delete(root.right, key);
    else {
        // Found the node to delete!
        if (root.left == null)
            return root.right;
        if (root.right == null)
            return root.left;

        // Two children: get successor
        root.val = minValue(root.right);
        root.right = delete(root.right,
                            root.val);
    }
    return root;
}

✅ BST Validation: Is This Really a BST?

Not every tree is a BST! We need to validate it.

The Trap 🪤

Just checking “left < parent < right” is NOT enough!

graph TD
    A["10"] --> B["5"]
    A --> C["15"]
    C --> D["6 - INVALID!"]
    C --> E["20"]

6 is less than its parent 15… but it’s in the RIGHT subtree of 10! This breaks the BST rule!

The Solution: Range Checking

Every node must be within a valid range:

boolean isValidBST(TreeNode root) {
    return validate(root,
        Long.MIN_VALUE, Long.MAX_VALUE);
}

boolean validate(TreeNode node,
                 long min, long max) {
    if (node == null) return true;

    if (node.val <= min || node.val >= max)
        return false;

    return validate(node.left, min, node.val)
        && validate(node.right, node.val, max);
}

Key insight: When going LEFT, update the MAX. When going RIGHT, update the MIN.

🎯 Inorder Successor & Predecessor

What Are They?

If you listed all BST values in sorted order, the:

• Successor = next value AFTER current
• Predecessor = value BEFORE current

graph TD
    A["20"] --> B["10"]
    A --> C["30"]
    B --> D["5"]
    B --> E["15"]
    C --> F["25"]
    C --> G["35"]

Sorted: 5, 10, 15, 20, 25, 30, 35

For node 20:

• Predecessor = 15 (before 20)
• Successor = 25 (after 20)

Finding Inorder Successor

Two cases:

Case 1: Node has RIGHT subtree → Go right, then keep going left!

Case 2: No right subtree → Go up until you’re a left child

TreeNode inorderSuccessor(TreeNode root,
                          TreeNode p) {
    TreeNode successor = null;

    while (root != null) {
        if (p.val < root.val) {
            successor = root;  // Potential!
            root = root.left;
        } else {
            root = root.right;
        }
    }

    return successor;
}

Finding Predecessor

Just flip the logic!

TreeNode predecessor(TreeNode root,
                     TreeNode p) {
    TreeNode pred = null;

    while (root != null) {
        if (p.val > root.val) {
            pred = root;  // Potential!
            root = root.right;
        } else {
            root = root.left;
        }
    }

    return pred;
}

🏆 Kth Smallest in BST

The Magic of Inorder Traversal

Remember: Inorder traversal of BST = Sorted order!

LEFT → ROOT → RIGHT gives you ascending order.

Example: Find 3rd Smallest

graph TD
    A["5"] --> B["3"]
    A --> C["6"]
    B --> D["2"]
    B --> E["4"]
    D --> F["1"]

Inorder: 1, 2, 3, 4, 5, 6

3rd smallest = 3 ✅

Solution: Count as You Go

int count = 0;
int result = 0;

int kthSmallest(TreeNode root, int k) {
    inorder(root, k);
    return result;
}

void inorder(TreeNode node, int k) {
    if (node == null) return;

    inorder(node.left, k);

    count++;
    if (count == k) {
        result = node.val;
        return;
    }

    inorder(node.right, k);
}

Time: O(H + k) where H is height!

🔄 Binary Search Tree Iterator

The Challenge

What if you can’t visit all nodes at once? You need to get one value at a time in sorted order!

The Trick: Controlled Inorder

Use a stack to remember where you are:

class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        pushLeft(node.right);
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

How It Works

graph TD
    A["7"] --> B["3"]
    A --> C["15"]
    B --> D["1"]
    C --> E["9"]
    C --> F["20"]

1. Start: Push 7, 3, 1 (go left)
2. next(): Pop 1, return 1
3. next(): Pop 3, push nothing, return 3
4. next(): Pop 7, push 15, 9, return 7
5. And so on…

Average O(1) per call! Space: O(H)

⚖️ Balanced BST Concepts

The Problem: Unbalanced Trees

If you insert 1, 2, 3, 4, 5 in order:

graph TD
    A["1"] --> B[" "]
    A --> C["2"]
    C --> D[" "]
    C --> E["3"]
    E --> F[" "]
    E --> G["4"]
    G --> H[" "]
    G --> I["5"]

This is basically a linked list! Search becomes O(n) instead of O(log n)! 😱

What is a Balanced BST?

A BST where the height difference between left and right subtrees is at most 1 for every node.

Height Matters!

Self-Balancing Trees

These trees automatically stay balanced:

AVL Rotations: The Balancing Act

When a tree becomes unbalanced, we rotate nodes:

Right Rotation (LL case):

graph TD
    subgraph Before
    A["30"] --> B["20"]
    A --> C[" "]
    B --> D["10"]
    B --> E[" "]
    end

→ Becomes →

graph TD
    subgraph After
    A["20"] --> B["10"]
    A --> C["30"]
    end

The balance is restored! 🎉

🎓 Quick Summary

🚀 You Did It!

You now understand Binary Search Trees! Remember:

1. BSTs organize data for fast searching
2. Left = smaller, Right = bigger
3. Inorder = sorted order (magic!)
4. Keep it balanced for best performance

The library metaphor isn’t just cute—it’s how databases, file systems, and search engines actually work!

Go build something amazing! 🌟