Introduction to Trees

Introduction

A tree is one of the most important graph structures in computer science. Trees are used in databases, file systems, compilers, AI, and countless other applications.

Definition

A tree is a connected, acyclic undirected graph.

Equivalently, a tree is:

• A connected graph with no cycles
• A connected graph with n vertices and (n-1) edges
• An acyclic graph where adding any edge creates a cycle
• A connected graph where removing any edge disconnects it
• A graph where exactly one path exists between any two vertices

Example: Basic Tree

      1
     / \
    2   3
   / \
  4   5

• 5 vertices, 4 edges
• No cycles
• Connected
• Unique path between any two vertices

Tree Terminology

Root

A root is a designated vertex at the top of a rooted tree.

Example:

      1 ← root
     / \
    2   3

Vertex 1 is the root.

Parent and Child

In a rooted tree:

• Parent: A vertex directly above and connected to another
• Child: A vertex directly below and connected to another

Example:

      1
     / \
    2   3 ← children of 1
   /
  4 ← child of 2

• 1 is parent of 2 and 3
• 2 is parent of 4
• 2 and 3 are children of 1

Siblings

Siblings are vertices with the same parent.

Example:

      1
     / \
    2   3 ← siblings (same parent 1)

Leaf (External Node)

A leaf is a vertex with no children (degree 1 in rooted tree, except root).

Example:

      1
     / \
    2   3 ← leaf
   / \
  4   5 ← leaves

Leaves: 3, 4, 5

Internal Node

An internal node is a non-leaf vertex (has at least one child).

Example: In above tree, internal nodes are 1, 2

Ancestors and Descendants

Ancestors of a vertex: All vertices on the path from the vertex to the root.

Descendants of a vertex: All vertices in the subtree rooted at that vertex.

Example:

      1
     / \
    2   3
   / \
  4   5

• Ancestors of 4: {2, 1}
• Descendants of 2: {4, 5}

Subtree

A subtree rooted at vertex v consists of v and all its descendants.

Example:

      1
     / \
    2   3  ← subtree rooted at 2:
   / \        {2, 4, 5}
  4   5

Level

The level of a vertex is its distance from the root.

Example:

Level 0:      1
             / \
Level 1:    2   3
           / \
Level 2:  4   5

• Root is at level 0
• Children of root at level 1
• etc.

Height

The height of a tree is the maximum level (longest path from root to a leaf).

Example:

      1
     / \
    2   3
   / \
  4   5

Height = 2 (path 1→2→4 has length 2)

Depth

The depth of a vertex is its level (distance from root).

Example:

• depth(1) = 0
• depth(2) = 1
• depth(4) = 2

Properties of Trees

Property 1: Unique Path

Theorem: In a tree, there is exactly one path between any two vertices.

Proof:

• At least one path exists (tree is connected)
• If two paths existed, they would form a cycle
• But trees are acyclic
• Therefore, exactly one path

Property 2: Edge Count

Theorem: A tree with n vertices has exactly (n-1) edges.

Proof (by induction):

• Base: n=1, edges=0 ✓
• Induction: Remove a leaf (degree 1)
  • Tree with (n-1) vertices has (n-2) edges
  • Adding back the leaf adds 1 edge
  • Total: (n-2) + 1 = n-1 edges ✓

Property 3: Adding Edge Creates Cycle

Theorem: Adding any edge to a tree creates exactly one cycle.

Proof:

• Tree already has one path between any two vertices
• Adding edge (u,v) creates second path
• These two paths form a cycle

Property 4: Removing Edge Disconnects

Theorem: Removing any edge from a tree disconnects it into two components.

Proof:

• There’s only one path between any two vertices
• Removing an edge removes the only path between its endpoints
• Graph becomes disconnected

Property 5: Minimum Connected

Theorem: A tree is a minimally connected graph (fewest edges while staying connected).

Proof:

• Has n-1 edges (minimum for connectivity)
• Removing any edge disconnects it
• Adding any edge creates a cycle (redundant)

Types of Trees

1. Rooted Tree

A tree with one designated vertex as the root.

Example:

      1 ← root
     /|\
    2 3 4

2. Binary Tree

A rooted tree where each vertex has at most 2 children (left and right).

Example:

      1
     / \
    2   3
   /
  4

3. Full Binary Tree

Every internal node has exactly 2 children.

Example:

      1
     / \
    2   3
   / \
  4   5

4. Complete Binary Tree

All levels are filled except possibly the last, which is filled from left to right.

Example:

      1
     / \
    2   3
   / \  /
  4  5 6

5. Perfect Binary Tree

All internal nodes have 2 children, and all leaves are at the same level.

Example:

      1
     / \
    2   3
   / \ / \
  4  5 6  7

6. Balanced Binary Tree

Height is O(log n) where n is the number of vertices.

7. m-ary Tree

Each vertex has at most m children.

Example (3-ary tree):

      1
    / | \
   2  3  4
  /|\
 5 6 7

8. Ordered Tree

Children of each vertex are ordered (left-to-right matters).

Forest

A forest is a collection of disjoint trees (acyclic graph, possibly disconnected).

Example:

Tree 1:     Tree 2:    Tree 3:
  1           4          6
 / \         / \
2   3       5   7

Properties:

• Forest with n vertices and k components has (n-k) edges
• Each component is a tree

Applications of Trees

1. File Systems

Root Directory
├── Documents
│   ├── file1.txt
│   └── file2.txt
└── Pictures
    └── photo.jpg

2. Organization Charts

CEO
├── CFO
│   ├── Accountant 1
│   └── Accountant 2
└── CTO
    └── Developer

3. Family Trees

Grandparents
├── Parent 1
│   ├── Child 1
│   └── Child 2
└── Parent 2

4. Decision Trees

Is it raining?
├── Yes → Take umbrella
└── No → No umbrella

5. Expression Trees

Expression: (a + b) * c

      *
     / \
    +   c
   / \
  a   b

6. Hierarchical Data

• XML/HTML DOM
• JSON structures
• Database indexes (B-trees)
• Huffman coding trees

Characterizations of Trees

A graph G with n vertices is a tree if it satisfies any two of:

1. G is connected
2. G is acyclic
3. G has (n-1) edges

Examples:

Connected + Acyclic → Tree Connected + (n-1) edges → Tree Acyclic + (n-1) edges → Tree

Counting Trees

Cayley’s Formula

The number of labeled trees on n vertices is n^(n-2).

Examples:

• n=2: 2^0 = 1 tree
• n=3: 3^1 = 3 trees
• n=4: 4^2 = 16 trees
• n=5: 5^3 = 125 trees

Unlabeled Trees

Counting unlabeled (non-isomorphic) trees is harder.

Examples:

• n=4: 2 unlabeled trees (path and star)
• n=5: 3 unlabeled trees
• n=6: 6 unlabeled trees

Tree Construction

From Degree Sequence

Example: Construct tree with degree sequence (3, 2, 1, 1, 1, 1, 1)

Solution:

• Vertex with degree 3 is center
• Connect to 3 vertices
• Vertex with degree 2 connects to 2 vertices
• Others are leaves

      1(deg=3)
     /|\
    2 3 4(deg=2)
         |
         5
   (vertices 2,3,5 are leaves)

Comparing Tree Types

Key Points for Exams

1. Tree: connected, acyclic graph
2. n vertices → (n-1) edges in tree
3. Unique path between any two vertices
4. Leaf: vertex with degree 1 (no children)
5. Root: designated top vertex
6. Height: longest path from root to leaf
7. Binary tree: at most 2 children per node
8. Forest: collection of disjoint trees
9. Adding edge to tree creates exactly one cycle
10. Removing edge from tree disconnects it

Practice Problems

1. How many edges does a tree with 10 vertices have?

2. Can a tree have a cycle? Explain.

3. Draw all non-isomorphic trees with 5 vertices.

4. What is the height of a complete binary tree with 15 vertices?

5. If a tree has 20 leaves and all internal nodes have degree 3, how many vertices total?

6. Is every connected acyclic graph a tree? Prove.

7. Draw a full binary tree of height 3.

8. How many labeled trees exist with 4 vertices? (Use Cayley’s formula)

9. Convert the expression “((a+b)*c)-d” to an expression tree.

10. In a rooted tree with 100 vertices, 30 are leaves. How many internal nodes?