Binary Search Trees

🌳 Binary Search Trees: Your Organized Bookshelf Adventure

Imagine you have a magical bookshelf where every book knows exactly where it belongs. Books with smaller numbers go left, bigger numbers go right. That’s a Binary Search Tree (BST)!

🎯 The One Analogy: The Smart Library

Think of a BST like a super-organized library where:

• Every shelf has ONE book in the middle
• Smaller-numbered books go to the LEFT shelf
• Bigger-numbered books go to the RIGHT shelf
• You can find ANY book super fast by just going left or right!

📚 BST Fundamentals

What Makes a BST Special?

A Binary Search Tree follows ONE golden rule:

Left child < Parent < Right child

       8        ← Parent
      / \
     3   10     ← 3 is smaller, 10 is bigger
    / \    \
   1   6    14

The BST Property

Every node in a BST must follow this rule:

• ALL nodes in left subtree are smaller
• ALL nodes in right subtree are bigger

Simple Example:

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

Think of each node as a library shelf card that remembers:

• Its own book number (val)
• Where the smaller books are (left)
• Where the bigger books are (right)

🔧 BST Core Operations

1. Search: Finding Your Book 📖

Looking for book #6? Start at the top!

def search(root, target):
    if not root:
        return None
    if target == root.val:
        return root  # Found it!
    if target < root.val:
        return search(root.left, target)
    return search(root.right, target)

How it works:

1. Start at root (book 8)
2. 6 < 8? Go LEFT to book 3
3. 6 > 3? Go RIGHT to book 6
4. Found it! 🎉

2. Insert: Adding a New Book 📝

New book goes to its PERFECT spot!

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

3. Delete: Removing a Book 🗑️

Three cases when removing:

Case 1: No children → Just remove it
Case 2: One child → Replace with child
Case 3: Two children → Use successor!

def delete(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:
        # Found the node to delete
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # Two children: get successor
        successor = find_min(root.right)
        root.val = successor.val
        root.right = delete(
            root.right, successor.val
        )
    return root

✅ BST Validation

Is This Really a BST?

Not every tree is a BST! We must CHECK.

Wrong approach: Only checking parent-child

     5
    / \
   3   7
  / \
 1   8  ← PROBLEM! 8 > 5 (root)

Right approach: Use MIN and MAX bounds

def is_valid_bst(root, min_val=float('-inf'),
                      max_val=float('inf')):
    if not root:
        return True
    if root.val <= min_val or root.val >= max_val:
        return False
    return (is_valid_bst(root.left,
                         min_val, root.val) and
            is_valid_bst(root.right,
                         root.val, max_val))

The Secret: Each node must stay within invisible fences!

⏭️ Inorder Successor and Predecessor

What Are They?

In the sorted order of all nodes:

• Successor = Next bigger value
• Predecessor = Previous smaller value

graph TD
    A["8"] --> B["3"]
    A --> C["10"]
    B --> D["1"]
    B --> E["6"]
    C --> F["14"]
    style E fill:#90EE90

For node 6: Successor = 8, Predecessor = 3

Finding Inorder Successor

def inorder_successor(root, p):
    successor = None
    while root:
        if p.val < root.val:
            successor = root  # Potential!
            root = root.left
        else:
            root = root.right
    return successor

Two Cases:

1. Has right child → Go right, then all the way left
2. No right child → Go up until you turn right

Finding Predecessor

def inorder_predecessor(root, p):
    predecessor = None
    while root:
        if p.val > root.val:
            predecessor = root
            root = root.right
        else:
            root = root.left
    return predecessor

🔢 Kth Smallest in BST

The Magic of Inorder Traversal

Inorder traversal of BST gives sorted order!

Tree:     5
         / \
        3   7
       / \
      2   4

Inorder: [2, 3, 4, 5, 7]

Find Kth Smallest

def kth_smallest(root, k):
    stack = []
    current = root
    count = 0

    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        count += 1
        if count == k:
            return current.val
        current = current.right
    return -1

Example: For k=3, we get 4 (the 3rd smallest)

🔄 Binary Search Tree Iterator

What’s an Iterator?

An iterator lets you get values ONE BY ONE in sorted order.

class BSTIterator:
    def __init__(self, root):
        self.stack = []
        self._push_left(root)

    def _push_left(self, node):
        while node:
            self.stack.append(node)
            node = node.left

    def next(self):
        node = self.stack.pop()
        self._push_left(node.right)
        return node.val

    def has_next(self):
        return len(self.stack) > 0

How It Works:

1. Start by going all the way LEFT
2. next() pops one, explores its right subtree
3. Always gives you the NEXT smallest!

# Usage:
iterator = BSTIterator(root)
while iterator.has_next():
    print(iterator.next())
# Prints: 1, 3, 6, 8, 10, 14

⚖️ Balanced BST Concepts

The Problem with Unbalanced Trees

Unbalanced:          Balanced:
    1                    4
     \                  / \
      2                2   6
       \              / \   \
        3            1   3   7
         \
          4

Unbalanced = SLOW! (Like a linked list)

What is Balance?

A tree is balanced when:

Height difference between left and right ≤ 1

Height of a Tree

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left),
                   height(root.right))

Check if Balanced

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left_h = check(node.left)
        right_h = check(node.right)
        if left_h == -1 or right_h == -1:
            return -1
        if abs(left_h - right_h) > 1:
            return -1
        return 1 + max(left_h, right_h)

    return check(root) != -1

Types of Balanced BSTs

Why Balance Matters

🎯 Quick Summary

graph TD
    A["BST Magic"] --> B["Left < Parent < Right"]
    A --> C["Core Ops"]
    A --> D["Special Skills"]
    C --> E["Search"]
    C --> F["Insert"]
    C --> G["Delete"]
    D --> H["Validate"]
    D --> I["Find Kth"]
    D --> J["Iterator"]
    D --> K["Balance Check"]

Remember These Keys:

1. BST Rule: Left < Parent < Right
2. Search: Go left for smaller, right for bigger
3. Validate: Use min/max bounds
4. Successor: Next bigger in sorted order
5. Kth Smallest: Inorder gives sorted list
6. Iterator: Stack-based traversal
7. Balance: Keep height differences small

🚀 You’ve Got This!

Binary Search Trees are like having a super-organized friend who always knows exactly where to find things. The key is that ONE simple rule: smaller goes left, bigger goes right.

Now you can:

• ✅ Build and navigate BSTs
• ✅ Check if a tree is valid
• ✅ Find successors and predecessors
• ✅ Get any Kth element efficiently
• ✅ Create iterators for smooth traversal
• ✅ Understand why balance matters

You’re now a BST master! 🌳✨