Trees and Heaps

🌳 Trees and Heaps: Your Guide to Family Tree Data Structures

Imagine you have a family tree on your wall. At the top is your great-grandparent. Below them are their children, and below those are grandchildren. That’s exactly how trees work in computer science — but instead of people, we store data!

🏡 Tree Fundamentals: The Family Tree Analogy

Think of a tree like an upside-down family tree.

What Makes a Tree?

• Root: The great-great-grandparent at the very top. Every tree has exactly ONE root.
• Node: Each family member (a box holding data).
• Edge: The lines connecting parent to child.
• Parent: A node with children below it.
• Child: A node connected below a parent.
• Leaf: A family member with NO children (the youngest generation).
• Siblings: Nodes sharing the same parent.
• Height: How many generations from root to the deepest leaf.

graph TD
    A["Grandma 👵 ROOT"] --> B["Mom 👩"]
    A --> C["Uncle 👨"]
    B --> D["You 🧒 LEAF"]
    B --> E["Sister 👧 LEAF"]
    C --> F["Cousin 🧒 LEAF"]

Why Use Trees?

Trees help organize data so we can:

• Find things fast (like finding a book in a library)
• Keep things sorted (alphabetical order, numbers in order)
• Show relationships (file folders on your computer!)

Real Life Example: Your computer’s folder system IS a tree!

• C:\ is the root
• Documents, Pictures are children
• Files inside are leaves

🌲 Binary Trees: The “Two Children Max” Rule

A binary tree is special. Each parent can have at most 2 children — a left child and a right child.

Think of it like this: Every parent has only two hands. They can only hold two children’s hands!

graph TD
    A["10"] --> B["5"]
    A --> C["15"]
    B --> D["3"]
    B --> E["7"]
    C --> F["12"]
    C --> G["20"]

Types of Binary Trees

Simple Example:

     🏠 (root)
    /    \
   🏠    🏠
  / \   / \
 🏠 🏠 🏠 🏠  ← Perfect Binary Tree!

🚶 Tree Traversal Methods: Taking a Walk Through the Tree

Traversal means visiting every node in a specific order. It’s like deciding how to visit every room in a house!

Three Main Ways to Walk

1. Pre-Order (Visit → Left → Right)

Visit the room FIRST, then go left, then right.

• “I look at the room, then explore left hallway, then right hallway”

2. In-Order (Left → Visit → Right)

Go left first, visit the room, then go right.

• “Check left hallway, look at room, check right hallway”
• Magic: For Binary Search Trees, this gives sorted order! ✨

3. Post-Order (Left → Right → Visit)

Go left, go right, THEN visit the room.

• “Explore everything else first, then look at this room”

Visual Example

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

Tip: For In-Order, imagine reading left-to-right at the bottom!

🔍 Binary Search Trees (BST): The Organized Library

A BST follows ONE simple rule:

Left children are SMALLER. Right children are BIGGER.

It’s like organizing a library:

• Books with titles A-M go LEFT
• Books with titles N-Z go RIGHT

graph TD
    A["50"] --> B["30"]
    A --> C["70"]
    B --> D["20"]
    B --> E["40"]
    C --> F["60"]
    C --> G["80"]

Finding 60:

1. Start at 50. Is 60 bigger? YES → Go RIGHT
2. At 70. Is 60 smaller? YES → Go LEFT
3. Found 60! 🎉

This takes only 3 steps instead of checking all 7 nodes!

⚙️ BST Operations: Adding, Finding, and Removing

🔹 Search: Finding a Value

To find 25 in BST:
Start at root (50)
  25 < 50 → go LEFT
At 30:
  25 < 30 → go LEFT
At 20:
  25 > 20 → go RIGHT
Not found! 25 isn't in tree.

🔹 Insert: Adding a New Value

Rule: Always add as a new LEAF (at the bottom).

To add 35:

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

graph TD
    A["50"] --> B["30"]
    A --> C["70"]
    B --> D["20"]
    B --> E["40"]
    E --> F["35 NEW!"]

🔹 Delete: Removing a Value

This is tricky! Three cases:

Example: Delete 30 (has two children)

1. Find next bigger: 35
2. Swap 30 and 35
3. Delete 30 from its new spot (now a leaf!)

⚖️ Self-Balancing Trees: Keeping Things Fair

Problem: If we add 1, 2, 3, 4, 5 in order, we get a crooked tree:

1
 \
  2
   \
    3  ← This is basically a list! Slow!
     \
      4

Solution: Self-balancing trees automatically fix themselves!

The Balance Rule

A tree is balanced when:

• Left side and right side have similar heights
• No side is much deeper than the other

Think of a seesaw — both sides should be about equal weight!

🎯 AVL Trees: The Perfectionist Tree

AVL trees are VERY strict about balance.

Rule: For EVERY node, the left and right heights can differ by at most 1.

Balance Factor

Balance Factor = Height(Left) - Height(Right)

• If BF is -1, 0, or 1 → Tree is balanced ✅
• If BF is 2 or -2 → Need to rotate! 🔄

Rotations: Fixing the Balance

When unbalanced, AVL trees rotate nodes like spinning a mobile.

Right Rotation (for left-heavy trees)

    30              20
   /               /  \
  20      →       10   30
 /
10

Left Rotation (for right-heavy trees)

10                  20
  \                /  \
   20      →     10   30
     \
      30

Left-Right Rotation

First rotate left, then rotate right.

Right-Left Rotation

First rotate right, then rotate left.

Real Example: Adding 1, 2, 3 to AVL:

1. Add 1 → [1]
2. Add 2 → [1→2]
3. Add 3 → Unbalanced! Left rotate!

  2
 / \
1   3  ← Now balanced!

📚 B-Trees: The Database Champion

B-Trees are special trees used in databases and file systems.

Key Difference: Each node can hold MULTIPLE values and have MANY children!

Why B-Trees?

Imagine a library with millions of books. A regular tree would be too tall (slow to climb). B-Trees are short and wide — like a 2-story building with HUGE floors!

B-Tree Rules (Order m)

• Each node holds up to m-1 keys
• Each node has up to m children
• All leaves are at the same level
• Tree grows from the middle, not bottom!

Example: B-Tree of Order 3

        [20|40]           ← Root holds 2 keys
       /   |   \
   [10] [25|30] [50|60]   ← Children

Searching for 25:

1. At root: 20 < 25 < 40 → Go middle
2. At [25|30]: Found 25! 🎉

Used in: MySQL, PostgreSQL, your computer’s file system!

🏔️ Heaps: The Priority Line

A heap is a special tree where:

• Max Heap: Parent is ALWAYS bigger than children (biggest on top!)
• Min Heap: Parent is ALWAYS smaller than children (smallest on top!)

Think of a VIP line:

• Max Heap = Most important person is always at the front
• Min Heap = Person with lowest ticket number is at front

graph TD
    subgraph Max Heap
    A["100"] --> B["50"]
    A --> C["30"]
    B --> D["20"]
    B --> E["10"]
    end

Why Heaps?

• Get the biggest or smallest item instantly (it’s always at the top!)
• Used in: Priority queues, scheduling tasks, finding top K items

Heap Property

Parent ≥ Children (Max Heap)
Parent ≤ Children (Min Heap)

BUT siblings don’t need to be in order! 30 and 50 aren’t sorted — and that’s OK!

🔧 Heap Operations: Insert and Extract

Insert: Adding to a Heap

1. Add at the bottom-right (next available spot)
2. Bubble up: Compare with parent, swap if needed, repeat!

Adding 90 to Max Heap:

     100              100
    /   \            /   \
   50   30    →     90   30
  / \              / \
 20  90           20  50
      ↑ Added here, then bubbled up!

Extract Max/Min: Removing the Top

1. Save the root (that’s our answer!)
2. Move last element to root
3. Bubble down: Swap with larger child until heap property restored

Extract Max from [100, 50, 30]:

     100              30               50
    /   \    →       /   \     →      /  \
   50   30          50                30

Result: 100

Building a Heap

Given [3, 1, 6, 5, 2, 4]:

1. Start with the array
2. Heapify from bottom-up (fix violations)

Max Heap Result:
      6
    /   \
   5     4
  / \   /
 1   2 3

🎓 Putting It All Together

🌟 Key Takeaways

1. Trees organize data in parent-child relationships
2. Binary trees limit each parent to 2 children
3. Traversals are different ways to visit all nodes
4. BST keeps things sorted: left=smaller, right=bigger
5. AVL trees auto-balance themselves using rotations
6. B-trees are wide and short — perfect for databases
7. Heaps always keep the max/min at the top

🎉 You did it! You now understand trees and heaps — the backbone of fast searching and sorting in computer science!

Remember: Every time you use a database, file explorer, or priority queue — trees are working behind the scenes! 🌲