20 - Spanning and Binary Trees - 9.3, 9.4, 9.5

ucla | MATH 61 | 2022-11-28T18:38

---

Table of Contents

• Definitions
• Big Ideas
  • Spanning Trees
    • Spanning Trees
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
  • Minimal Spanning Trees (MST)
    • Prim’s Algorithm
  • Binary Tree
    • Binary Tree
    • Full Binary Tree
    • Thm. Full Binary Tree
• Resources

Definitions

---

• internal vertices
  • vertices that are not “leaf nodes”
• leaf nodes / terminal vertices
  • “dead end” vertices in a tree

Big Ideas

---

Spanning Trees

Spanning Trees

• subgraph $T$ of $G$ s.t. $T$ is a tree where $V(T)=V(G)$

• e.g. spanning trees

Breadth First Search (BFS)

• e.g. visual

Depth First Search (DFS)

• e.g. visual

Minimal Spanning Trees (MST)

• the spanning tree of weighted graph $G$ whose sum of weights is the lowest

Prim’s Algorithm

• e.g. visual

Binary Tree

Binary Tree

• a rooted tree where each vertex has $n\in 0,1,2$ children
• the children are labeled as “right” or “left”

• e.g. visual

Full Binary Tree

• a binary tree with each vertex having $n\in 0,2$ children

Thm. Full Binary Tree

• if full binary tree $T$ has $i$ internal vertices
• $⟹i+1$ terminal vertices (leaf nodes)

• $\implies

  V(T)

  = 2i+1$

Resources

---

📌

**SUMMARY
**