Binary Search Trees

🌳 Binary Search Trees: Your Magical Library Adventure

Imagine you’re a librarian in a magical library. Every book has a number on its spine. Your job? Find any book super fast! But how? You build a Binary Search Tree — a special way to organize books so you can find any one in seconds.

📚 BST Fundamentals: The Magic Rule

What is a BST?

A Binary Search Tree is like a family tree for numbers. Each “person” (we call them nodes) can have at most two children — a left child and a right child.

The Golden Rule:

• Left child = smaller numbers
• Right child = bigger numbers

Simple Example:

       8
      / \
     3   10
    / \    \
   1   6    14

• 8 is the “boss” (root)
• 3 is smaller than 8 → goes left
• 10 is bigger than 8 → goes right
• 1 is smaller than 3 → goes left of 3
• 6 is bigger than 3 → goes right of 3

Why is this Magic?

Think about finding book #6:

1. Start at 8: Is 6 smaller? Yes! Go left.
2. At 3: Is 6 bigger? Yes! Go right.
3. Found 6! 🎉

You only checked 3 books out of 6. That’s the magic!

graph TD
    A["8"] --> B["3"]
    A --> C["10"]
    B --> D["1"]
    B --> E["6"]
    C --> F["14"]
    style A fill:#ff6b6b,color:white
    style E fill:#4ecdc4,color:white

🔧 BST Core Operations: The Librarian’s Toolkit

1. SEARCH: Finding a Book

To find a number, ask yourself at each stop:

• Is this the number? Done!
• Is my number smaller? Go left.
• Is my number bigger? Go right.

function search(node, value) {
  if (!node) return null;
  if (value === node.val) return node;
  if (value < node.val) {
    return search(node.left, value);
  }
  return search(node.right, value);
}

2. INSERT: Adding a New Book

Same logic as search! Go left or right until you find an empty spot.

function insert(node, value) {
  if (!node) {
    return { val: value,
             left: null,
             right: null };
  }
  if (value < node.val) {
    node.left = insert(node.left, value);
  } else {
    node.right = insert(node.right, value);
  }
  return node;
}

Example: Insert 5 into our tree:

1. 5 < 8 → go left
2. 5 > 3 → go right
3. 5 < 6 → go left (empty!) → Insert here!

3. DELETE: Removing a Book

This is trickier. Three cases:

function deleteNode(node, value) {
  if (!node) return null;
  if (value < node.val) {
    node.left = deleteNode(node.left, value);
  } else if (value > node.val) {
    node.right = deleteNode(node.right, value);
  } else {
    // Found it!
    if (!node.left) return node.right;
    if (!node.right) return node.left;
    // Two children: find successor
    let succ = node.right;
    while (succ.left) succ = succ.left;
    node.val = succ.val;
    node.right = deleteNode(
      node.right, succ.val
    );
  }
  return node;
}

✅ BST Validation: Is This Really a BST?

Not every tree is a valid BST! We need to check the Golden Rule everywhere.

Trap: You can’t just check parent-child. You need ranges!

       5
      / \
     1   7
        / \
       3   9  ← 3 is wrong!

3 is smaller than 7, so it’s valid as 7’s left child… BUT 3 is also smaller than 5, and it’s in the RIGHT subtree of 5. Invalid!

The Smart Way: Track min and max allowed values.

function isValidBST(node, min, max) {
  if (!node) return true;
  if (node.val <= min ||
      node.val >= max) {
    return false;
  }
  return isValidBST(
    node.left, min, node.val
  ) && isValidBST(
    node.right, node.val, max
  );
}

// Call with:
// isValidBST(root, -Infinity, Infinity)

🔄 Inorder Successor and Predecessor

What Are They?

If you listed all numbers in order (1, 3, 6, 8, 10, 14), each number has:

• Successor: The next bigger number
• Predecessor: The previous smaller number

Finding Inorder Successor

Two cases:

1. Has right child? Go right, then all the way left.
2. No right child? Go up until you come from a left child.

function inorderSuccessor(root, p) {
  if (p.right) {
    let node = p.right;
    while (node.left) {
      node = node.left;
    }
    return node;
  }
  let successor = null;
  while (root) {
    if (p.val < root.val) {
      successor = root;
      root = root.left;
    } else {
      root = root.right;
    }
  }
  return successor;
}

Finding Inorder Predecessor

Opposite logic:

1. Has left child? Go left, then all the way right.
2. No left child? Go up until you come from a right child.

🏆 Kth Smallest in BST

Remember how inorder traversal gives us sorted order? We use that!

The Trick: Do inorder traversal, count as you go, stop at K.

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node || result !== null) {
      return;
    }
    inorder(node.left);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }

  inorder(root);
  return result;
}

Example: Find 3rd smallest in our tree:

       8
      / \
     3   10
    / \    \
   1   6    14

Inorder: 1, 3, 6, 8, 10, 14

3rd smallest = 6 🎯

🎮 Binary Search Tree Iterator

What if you want to get BST values one at a time, in order? Like a “next” button!

The Challenge: You can’t store all values (too much memory for huge trees).

The Smart Way: Use a stack to remember where you are.

class BSTIterator {
  constructor(root) {
    this.stack = [];
    this.pushLeft(root);
  }

  pushLeft(node) {
    while (node) {
      this.stack.push(node);
      node = node.left;
    }
  }

  next() {
    let node = this.stack.pop();
    this.pushLeft(node.right);
    return node.val;
  }

  hasNext() {
    return this.stack.length > 0;
  }
}

How it works:

1. Start by pushing all leftmost nodes
2. next(): Pop one, push its right subtree’s leftmost
3. Magic! Always gives you the next smallest.

graph TD
    A["Create Iterator"] --> B["Push all left nodes to stack"]
    B --> C["Call next"]
    C --> D["Pop from stack"]
    D --> E[Push right subtree's left nodes]
    E --> F["Return popped value"]
    F --> C

⚖️ Balanced BST Concepts

The Problem with Unbalanced Trees

What if you insert 1, 2, 3, 4, 5 in order?

1
 \
  2
   \
    3
     \
      4
       \
        5

This is basically a linked list! Finding 5 takes 5 steps. 😢

What is Balanced?

A balanced BST keeps both sides roughly equal height.

Height Rule: Left and right subtrees differ by at most 1 level.

Self-Balancing Trees

Famous types:

• AVL Trees: Strictly balanced, rotates after every insert
• Red-Black Trees: Loosely balanced, faster inserts

Rotations: The Balancing Act

When a tree gets unbalanced, we rotate nodes.

Right Rotation:

    3           2
   /           / \
  2     →     1   3
 /
1

Left Rotation:

1               2
 \             / \
  2     →     1   3
   \
    3

graph TD
    A["Unbalanced"] --> B["Check Balance Factor"]
    B --> C{Factor > 1?}
    C -->|Yes| D["Left Heavy - Rotate Right"]
    C -->|No| E{Factor < -1?}
    E -->|Yes| F["Right Heavy - Rotate Left"]
    E -->|No| G["Already Balanced!"]

Balance Factor

For any node: Balance = Height(Left) - Height(Right)

🌟 The Big Picture

graph LR
    A["BST Mastery"] --> B["Fundamentals"]
    A --> C["Operations"]
    A --> D["Validation"]
    A --> E["Navigation"]
    A --> F["Balance"]

    B --> B1["Left < Parent < Right"]
    C --> C1["Search/Insert/Delete"]
    D --> D1["Use Min-Max Ranges"]
    E --> E1["Successor/Predecessor"]
    E --> E2["Kth Smallest"]
    E --> E3["Iterator Pattern"]
    F --> F1["Rotations"]
    F --> F2["Height Balance"]

Key Takeaways

1. BST = Organized Library — Everything in its place
2. Operations are O(log n) — When balanced!
3. Validation needs ranges — Don’t just check parent-child
4. Inorder = Sorted — This is your superpower
5. Balance matters — Unbalanced = slow

🎯 Quick Reference

Remember: A balanced BST is a happy BST! 🌳✨