Trees

What Is a Tree?

A tree is a connected graph with no cycles. Trees are fundamental data structures in computer science and have many important properties.

Properties of Trees:
  1. Connected
  2. No cycles (acyclic)
  3. For n vertices: exactly n - 1 edges
  4. There is exactly one path between any two vertices
  5. Adding one edge creates exactly one cycle
  6. Removing any edge disconnects the tree

Rooted Trees

Root:       The top vertex (designated parent)
Parent:     The vertex above in the hierarchy
Child:      A vertex directly below
Leaf:       A vertex with no children (terminal node)
Internal:   A vertex that has children
Height:     The length of the longest path from root to leaf
Depth:      The length of the path from root to a vertex

        Root (A)
       /    \
      B      C
     / \      \
    D   E      F
   Leaves: D, E, F
   Height: 2

Spanning Trees

A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices of G.

Properties:
  A connected graph with n vertices has at least one spanning tree
  A spanning tree has exactly n - 1 edges
  Removing any edge from G may create multiple spanning trees

Applications:
  Network design (minimum cost connections)
  Finding minimum spanning tree (Kruskal's, Prim's algorithms)