Lesson 12 — Intermediate

Trees & Spanning Trees

Tree graph theory ka sabse important special case hai — connected graph bina cycle ke. Is lesson mein seekhenge tree ki properties (n−1 edges), spanning tree, minimum spanning tree (Kruskal-Prim), Cayley formula aur binary trees. Har network design isi par chalta hai.

Tree kya hai

Tree ka golden rule: n vertices ho toh exactly n − 1 edges. Ek aur edge jod do toh cycle ban jaayegi, tree nahi rahega. Ye relation exam mein bar bar aata hai.

Tree ki properties

Tree ki properties (n vertices wala tree):

1) Edges = n − 1 (zyada → cycle, kam → disconnected)
2) Connected + (n−1) edges → tree (equivalent definition)
3) Connected + acyclic → tree
4) n ≥ 2 wale tree mein kam se kam 2 LEAF hote hain
   (leaf = degree 1 ka vertex)
5) Koi do vertices ke beech EXACTLY EK unique path
   (unique path hi cycle na hone ka proof hai)

Proof sketch (1 aur 2):
  Tree = connected + acyclic. n vertices ko jodne ke liye
  n−1 edges hi kaafi hain; ek aur edge jodne par do
  vertices ke beech doosra path = cycle pakki.

Spanning tree aur MST

Spanning tree = uske SARE vertices cover karne wala subgraph jo tree ho. Naya network bana rahe ho toh sabse kam wire = spanning tree (aur minimum spanning tree):

Spanning Tree : graph ka wo TREE jo SARE vertices cover kare
  n vertices → spanning tree mein bhi n − 1 edges
  (extra edges hata do, vertices connect rehne chahiye)

Minimum Spanning Tree (MST) : total weight minimum
  KRUSKAL : edges weight se sort → chhoti se chhoti add karo
            (agar cycle na banaye) — greedy, edge-based
  PRIM    : ek vertex se shuru → har step nearest edge add
            — greedy, vertex-based
  (dono ka TOTAL weight same aata hai — answer unique)

Cayley formula : K_n (complete graph) ke spanning trees
  = n^(n−2)      K4 → 4² = 16 spanning trees

Kruskal aur Prim dono greedy algorithms hain — fark sirf approach mein hai. Kruskal edges ko sort karta hai, Prim vertex se grow karta hai. Dono ka MST weight same — ye GATE mein verify karne wala question ban jaata hai.

Binary trees

BINARY TREE : har node ke max 2 children (left, right)

FULL      : har node 0 ya 2 children
COMPLETE  : har level full + last level left se

Height h (root = level 0):
  Level h pe max 2^h nodes
  Total max = 2^0 + 2^1 + ... + 2^h = 2^(h+1) − 1
  Example: h = 3 → max 15 nodes

Level 1 se count karo (root = level 1) toh total = 2^h − 1

Full binary tree: leaves = internal nodes + 1
  (10 internal nodes → 11 leaves)

n nodes ki height: worst case n − 1 (skewed),
balanced case ≈ log₂ n (BST search isi par depend karta hai)

• Tree mein har do vertices ka unique path — isi liye routing protocols tree maintain karte hain (loop banne pe broadcast storm hota hai).
• BST property: left subtree ka sab node < root < right subtree ka sab node — search O(height) mein.
• Heap: complete binary tree + parent ka value children se order mein (min ya max heap).

Exercise

Common mistakes

• n edges wale graph ko tree samajhna: n vertices par tree = n − 1 edges. n edges toh cycle wala graph hai (ya koi component alag). Rule ulta mat lagao.
• MST aur shortest path mix: MST poore graph ka minimum total wiring hai (sare vertices cover). Shortest path sirf do vertices ke beech. Alag problems, alag algorithms.
• Height ka level count galat: Root = level 0 ho toh height h par max 2^(h+1) − 1 nodes; root = level 1 ho toh 2^h − 1. Question ka convention hamesha padho.

Houses = vertices, pipes = edges
n ghar → n − 1 pipe (tree, bina loop)
Ek aur pipe jod di → cycle = wastage + pressure issue
MST (Kruskal/Prim) = sabse sasta pipeline plan
Cayley n^(n−2) : n ghar ka full network = itne tree plans