Skip to content

Chapter 11: Trees, Spanning Trees, Directed Trees, and Binary Trees

(TB1 Ch.5, Articles 3–6)

1. Tree

Definition

A tree is a connected, acyclic, undirected graph.

  • Connected: There is a path between every pair of vertices.
  • Acyclic: No cycles exist.

Properties of a Tree

  1. If a tree has (n) vertices, it has exactly (n-1) edges.
  2. There is exactly one path between any two vertices.
  3. Adding any edge creates a cycle; removing any edge disconnects the graph.

Example

Vertices: {A, B, C, D} Edges: {AB, AC, AD}

  • Tree (star-shaped)
  • Number of edges = 4 - 1 = 3 ✅

2. Rooted Tree / Directed Tree

Definition

A rooted tree is a tree with one designated vertex as the root.

  • All edges are directed away from or towards the root
  • Each vertex has one parent (except root) and zero or more children

Directed Tree (Arborescence)

  • Directed edges in a rooted tree → directed tree
  • Out-degree of root ≥ 0, in-degree of root = 0

Example

Root = A Edges: A → B, A → C, C → D

      A
     / \
    B   C
         \
          D

3. Spanning Tree

Definition

A spanning tree of a connected graph G is a subgraph that:

  1. Includes all vertices of G

  2. Is a tree (connected and acyclic)

  3. A graph can have many spanning trees

Example

Graph: V = {1,2,3,4}, E = {12, 13, 14, 23}

  • Spanning tree edges: {12,13,14} ✅
  • Leaves out edge 23 to avoid cycles

Properties

  1. Spanning tree of a graph with (n) vertices → (n-1) edges
  2. Minimum Spanning Tree (MST): spanning tree with minimum sum of edge weights (important in network design)

4. Binary Tree

Definition

A binary tree is a rooted tree where each node has at most two children.

  • Left child and Right child
  • Common in data structures (BST, heaps)

Special Types

  1. Full Binary Tree: Every node has 0 or 2 children
  2. Complete Binary Tree: All levels except possibly last are fully filled; last level left-aligned
  3. Perfect Binary Tree: All levels completely filled

Properties

  • Maximum nodes at level (i) = (2^i) (root at level 0)
  • Height (h) → Maximum nodes = (2^{h+1} - 1)
  • Number of leaf nodes in full binary tree = number of internal nodes + 1

Example

        1
       / \
      2   3
     / \
    4   5
  • Root = 1
  • Leaves = 3, 4, 5
  • Internal nodes = 1, 2

5. Applications in Computer Science

  • Trees: Hierarchical data (file systems, organizational charts)
  • Spanning Trees: Network design, MST, routing algorithms
  • Directed Trees: Expression trees, parse trees
  • Binary Trees: Search trees (BST), heaps, Huffman coding, decision trees

Comments