Trees as Graphs - Learning Module

Loading content...

0/276

Tree Properties in Graph Terms

Measuring Trees with Graph Theory

When we studied trees as data structures, we used terms like 'height,' 'depth,' and 'balanced.' But these concepts were often tied to specific rooted tree implementations. Graph theory provides a more general vocabulary—diameter, radius, center, eccentricity—that applies to trees regardless of whether they're rooted.

These properties aren't merely academic. They appear in practical problems: finding the optimal location for a server in a network, computing the longest path in a tree, or determining how 'balanced' a tree is in a fundamental sense. Understanding them through graph theory reveals their true nature.

What You Will Learn

By the end of this page, you will understand key tree metrics (diameter, radius, center, eccentricity) in graph-theoretic terms, learn algorithms to compute these properties efficiently, see how the unique path property of trees enables elegant solutions, and understand how rooted tree concepts (height, depth) relate to these fundamental measures.

Eccentricity: Distance to the Farthest Vertex

The eccentricity of a vertex is the most fundamental distance-based property. It measures how 'central' or 'peripheral' a vertex is in the tree.

Definition: The eccentricity of a vertex v, denoted ecc(v), is the maximum distance from v to any other vertex in the graph.

ecc(v) = max{ d(v, u) : u ∈ V }

where d(v, u) is the length of the unique path between v and u.

Intuition: If you stand at vertex v, your eccentricity tells you the farthest you'd ever have to travel to reach any other vertex. A low eccentricity means you're 'central'—close to everything. A high eccentricity means you're on the 'periphery.'

Converting Mermaid diagram...

In the tree above, let's compute eccentricities:

ecc(A) = max distance from A = d(A, F) = 4
ecc(B) = max distance from B = d(B, F) = 3
ecc(C) = max distance from C = d(C, A) = d(C, F) = 2
ecc(D) = max distance from D = d(D, A) = 3
ecc(E) = max distance from E = d(E, F) = 3
ecc(F) = max distance from F = d(F, A) = 4

Vertex C has the lowest eccentricity (2)—it's the most 'central.' Vertices A and F have the highest (4)—they're on the periphery.

eccentricity.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from collections import defaultdict, deque
from typing import Dict, List, Tuple
 
def compute_eccentricities(n: int, edges: List[Tuple[int, int]]) -> Dict[int, int]:
    """
    Compute the eccentricity of every vertex in the tree.
    
    Approach: BFS from each vertex to find max distance.
    Time Complexity: O(n²) - n BFS traversals, each O(n)
    
    Note: For trees, more efficient O(n) algorithms exist using
    the diameter endpoints, but this demonstrates the concept clearly.
    """
    # Build adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    def bfs_farthest(start: int) -> Tuple[int, int]:
        """BFS to find max distance from start"""
        dist = {start: 0}
        queue = deque([start])
        farthest_node = start
        max_dist = 0
        
        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                if neighbor not in dist:
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
                    if dist[neighbor] > max_dist:
                        max_dist = dist[neighbor]
                        farthest_node = neighbor
        
        return farthest_node, max_dist
    
    eccentricities = {}
    for v in range(n):
        _, max_dist = bfs_farthest(v)
        eccentricities[v] = max_dist
    
    return eccentricities
 
# Example
edges = [(0, 1), (1, 2), (2, 3), (2, 4), (3, 5)]  # A-B-C-D-F and C-E
ecc = compute_eccentricities(6, edges)
for v in sorted(ecc.keys()):
    print(f"Eccentricity of {v}: {ecc[v]}")

Diameter: The Longest Path in the Tree

The diameter is perhaps the most famous tree property. It represents the 'longest stretch' of the tree—the farthest apart any two vertices can be.

Definition: The diameter of a tree is the maximum distance between any pair of vertices.

diameter(T) = max{ d(u, v) : u, v ∈ V }

Equivalently, the diameter is the maximum eccentricity of any vertex:

diameter(T) = max{ ecc(v) : v ∈ V }

Key Properties:

The diameter path is the longest simple path in the tree
The diameter is unique (there's exactly one longest distance), but multiple pairs may achieve it
In a tree, the diameter can be computed in O(n) time using a clever double-BFS trick

The Two-BFS Trick

To find the diameter of a tree: (1) BFS from any vertex X to find the farthest vertex A. (2) BFS from A to find the farthest vertex B. The distance A to B is the diameter. This works because an endpoint of any diameter must be one of the farthest vertices from any starting point.

diameter.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
from collections import defaultdict, deque
from typing import List, Tuple
 
def tree_diameter(n: int, edges: List[Tuple[int, int]]) -> Tuple[int, List[int]]:
    """
    Find the diameter of a tree and return the diameter path.
    
    Algorithm (Two-BFS method):
    1. BFS from any node to find one endpoint of diameter
    2. BFS from that endpoint to find the other endpoint
    3. The distance is the diameter; we can also reconstruct the path
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    
    Why it works: From any vertex x, the farthest vertex must be an 
    endpoint of some diameter. BFS from that endpoint finds the full diameter.
    """
    if n == 1:
        return 0, [0]
    
    # Build adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    def bfs_farthest(start: int) -> Tuple[int, int, dict]:
        """Returns (farthest_node, distance, parent_map) from start"""
        dist = {start: 0}
        parent = {start: -1}
        queue = deque([start])
        farthest = start
        max_dist = 0
        
        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                if neighbor not in dist:
                    dist[neighbor] = dist[node] + 1
                    parent[neighbor] = node
                    queue.append(neighbor)
                    if dist[neighbor] > max_dist:
                        max_dist = dist[neighbor]
                        farthest = neighbor
        
        return farthest, max_dist, parent
    
    # Step 1: BFS from arbitrary node (0) to find one diameter endpoint
    endpoint_a, _, _ = bfs_farthest(0)
    
    # Step 2: BFS from endpoint_a to find the other endpoint (and diameter)
    endpoint_b, diameter, parent = bfs_farthest(endpoint_a)
    
    # Step 3: Reconstruct the diameter path
    path = []
    current = endpoint_b
    while current != -1:
        path.append(current)
        current = parent[current]
    
    return diameter, path
 
# Example
edges = [(0, 1), (1, 2), (2, 3), (2, 4), (3, 5)]
diameter, path = tree_diameter(6, edges)
print(f"Diameter: {diameter}")
print(f"Diameter path: {path}")  # One of the longest paths

Application: Server Placement

Imagine placing a server in a network (tree topology) to minimize maximum latency to any client. The optimal location is at the center of the diameter path! This minimizes the longest distance to any node.

Connection to Rooted Tree Height:

If you root a tree at one endpoint of the diameter, the tree's height equals the diameter. If you root at the center, the height is minimized and equals ⌈diameter/2⌉. This reveals the deep connection between diameter and the concept of 'balance.'

Radius and Center: The Heart of the Tree

While the diameter captures the 'maximum extent' of the tree, the radius and center capture the 'tightest core.'

Definition: The radius of a tree is the minimum eccentricity of any vertex.

radius(T) = min{ ecc(v) : v ∈ V }

Definition: The center of a tree is the set of vertices with minimum eccentricity (equal to the radius).

center(T) = { v ∈ V : ecc(v) = radius(T) }

Remarkable Property: In a tree, the center contains at most two vertices, and if there are two, they are adjacent. The center lies at the midpoint of any diameter path.

Diameter, Radius, and Center Relationships
Property	Definition	Relationship
Diameter	max eccentricity	Longest path length
Radius	min eccentricity	radius = ⌈diameter/2⌉
Center	vertices with min eccentricity	1 or 2 vertices; midpoint of diameter
Peripheral vertices	vertices with max eccentricity	Endpoints of diameter paths

center.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import defaultdict, deque
from typing import List, Tuple
 
def find_tree_center(n: int, edges: List[Tuple[int, int]]) -> List[int]:
    """
    Find the center of a tree (1 or 2 vertices).
    
    Efficient Algorithm: Iteratively remove leaves until 1-2 vertices remain.
    The remaining vertices are the center.
    
    Why it works: Removing all leaves decreases all non-leaf eccentricities
    by 1, preserving which vertices have minimum eccentricity. We stop when
    only the center remains.
    
    Time Complexity: O(n)
    Space Complexity: O(n)
    """
    if n == 1:
        return [0]
    if n == 2:
        return [0, 1]  # Both are center
    
    # Build adjacency list and track degrees
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    
    # Find initial leaves (degree 1)
    leaves = deque([v for v in range(n) if len(adj[v]) == 1])
    remaining = n
    
    # Iteratively remove leaves
    while remaining > 2:
        new_leaves = deque()
        leaves_to_remove = len(leaves)
        remaining -= leaves_to_remove
        
        for _ in range(leaves_to_remove):
            leaf = leaves.popleft()
            # Get the single neighbor
            for neighbor in adj[leaf]:
                adj[neighbor].remove(leaf)
                if len(adj[neighbor]) == 1:
                    new_leaves.append(neighbor)
            adj[leaf].clear()
        
        leaves = new_leaves
    
    # Remaining vertices are the center
    return [v for v in range(n) if len(adj[v]) > 0 or remaining == 1 and v == leaves[0] if leaves else v in [node for node in range(n) if adj[node]]]
 
def find_tree_center_clean(n: int, edges: List[Tuple[int, int]]) -> List[int]:
    """Cleaner implementation using tracking"""
    if n == 1:
        return [0]
    
    adj = defaultdict(set)
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    
    degree = [len(adj[v]) for v in range(n)]
    leaves = deque([v for v in range(n) if degree[v] == 1])
    remaining = n
    
    while remaining > 2:
        next_leaves = deque()
        for _ in range(len(leaves)):
            leaf = leaves.popleft()
            remaining -= 1
            for neighbor in adj[leaf]:
                degree[neighbor] -= 1
                if degree[neighbor] == 1:
                    next_leaves.append(neighbor)
        leaves = next_leaves
    
    return list(leaves)
 
# Example
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (2, 5)]
center = find_tree_center_clean(6, edges)
print(f"Tree center: {center}")

Why At Most Two Centers?

The proof is elegant: The center lies on every diameter path, at the midpoint. If the diameter is even, the midpoint is a single vertex (one center). If odd, the midpoint is an edge, giving two adjacent centers. There cannot be three, as that would require multiple diameter paths with different midpoints—impossible in a tree.

Height and Depth Through the Graph Lens

In rooted tree contexts, height and depth are fundamental concepts. Graph theory reveals their deeper nature.

Height and Depth Definitions

•Depth of vertex v (rooted context): Distance from root to v. Equals d(root, v) in graph terms.
•Height of vertex v: Maximum distance from v to any leaf in its subtree. (Rooted context)
•Height of the tree: Height of the root = maximum depth of any vertex.
•Graph-theoretic equivalent: Height of tree rooted at r = ecc(r) = eccentricity of r.

Key Insight: When you root a tree at vertex r, the tree's height is exactly the eccentricity of r.

Rooting at a peripheral vertex (max eccentricity) gives maximum height = diameter
Rooting at the center gives minimum height = radius = ⌈diameter/2⌉

This explains why 'balanced' trees (like AVL trees) work to keep the root near the center—minimizing height, which controls operation complexity.

Root Position and Tree Height
Root Position	Tree Height	Insight
At center	radius = ⌈diameter/2⌉	Minimum possible height; most balanced
At diameter endpoint	diameter	Maximum height; least balanced
Arbitrary vertex v	ecc(v)	Height equals vertex's eccentricity

height_by_root.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
from collections import defaultdict, deque
from typing import List, Tuple
 
def tree_height_by_root(n: int, edges: List[Tuple[int, int]], root: int) -> int:
    """
    Compute the height of the tree when rooted at 'root'.
    
    This is equivalent to computing the eccentricity of 'root'.
    Height = max distance from root to any other vertex.
    """
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # BFS to find max distance from root
    dist = {root: 0}
    queue = deque([root])
    max_dist = 0
    
    while queue:
        node = queue.popleft()
        for neighbor in adj[node]:
            if neighbor not in dist:
                dist[neighbor] = dist[node] + 1
                max_dist = max(max_dist, dist[neighbor])
                queue.append(neighbor)
    
    return max_dist
 
def analyze_all_roots(n: int, edges: List[Tuple[int, int]]):
    """Show how height varies with root choice"""
    heights = [(root, tree_height_by_root(n, edges, root)) for root in range(n)]
    
    print("Root  | Height (Eccentricity)")
    print("-" * 30)
    for root, height in heights:
        print(f"  {root}   |   {height}")
    
    min_height = min(h for _, h in heights)
    max_height = max(h for _, h in heights)
    centers = [r for r, h in heights if h == min_height]
    periphery = [r for r, h in heights if h == max_height]
    
    print(f"\nRadius (min height): {min_height}")
    print(f"Diameter (max height): {max_height}")
    print(f"Center vertices: {centers}")
    print(f"Peripheral vertices: {periphery}")
 
# Example: a path graph
edges = [(0, 1), (1, 2), (2, 3), (3, 4)]  # Path: 0-1-2-3-4
print("Path graph analysis:")
analyze_all_roots(5, edges)
 
# Example: a more complex tree
print("\nComplex tree analysis:")
tree_edges = [(0, 1), (1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
analyze_all_roots(7, tree_edges)

Vertex Degree and Structural Properties

The degree of a vertex—the number of edges incident to it—reveals structural information about the tree.

Degree-Based Vertex Classification

•Leaves: Vertices with degree 1. In a tree with n > 1 vertices, there's at least one leaf (in fact, at least two).
•Internal vertices: Vertices with degree ≥ 2. These are the 'branching points' of the tree.
•Maximum degree (Δ): The highest degree of any vertex. Related to tree 'bushiness.'
•Binary trees: Internal vertices have degree ≤ 3 (at most 2 children + 1 parent when rooted).

The Degree Sum Formula:

For any undirected graph, the sum of all vertex degrees equals twice the number of edges:

∑ deg(v) = 2|E|

For a tree with n vertices: ∑ deg(v) = 2(n-1) = 2n - 2

Consequence: The average degree in a tree is 2 - 2/n, approaching 2 as n grows. Trees are inherently 'sparse' graphs.

Counting Leaves:

If we denote nₖ as the number of vertices with degree k, then:

n₁ (leaves) = 2 + ∑(k-2)·nₖ for k ≥ 3

This formula reveals: the more high-degree internal nodes, the more leaves a tree must have.

Degree Constraints in Tree Types
Tree Type	Degree Constraint	Implication
Path	All vertices degree ≤ 2	Linear structure; diameter = n-1
Binary Tree (rooted)	Max degree 3	At most 2 children per node
Star	Center has degree n-1; others degree 1	Diameter = 2; center is unique
Complete k-ary Tree	Internal nodes have k children	Regular branching structure
General Tree	No constraint	Maximum flexibility

Leaf Removal Invariant

Removing a leaf from a tree with n ≥ 2 vertices yields a tree with n-1 vertices. This invariant underlies many tree algorithms: we can process trees by iteratively handling leaves, confident the structure remains a valid tree.

Path Properties in Trees

The unique path property—the guarantee that exactly one simple path exists between any two vertices—is arguably the defining characteristic of trees. It enables elegant algorithms and closed-form analyses.

Consequences of Unique Paths

•Deterministic distances: d(u, v) is unambiguous—there's only one path to measure
•No shortest path algorithms needed: Finding the path IS finding the shortest path
•Efficient LCA: In rooted trees, paths from u and v to root meet at exactly one vertex (LCA)
•Tree decomposition: Any edge (u, v) splits the tree into exactly two subtrees
•Path counting: Number of paths between pairs = exactly n(n-1)/2 (one per unordered pair)

path_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
from collections import defaultdict
from typing import List, Tuple
 
def path_between(adj: dict, u: int, v: int) -> List[int]:
    """
    Find the unique path between u and v in a tree.
    
    Since there's exactly one path, simple DFS suffices.
    No need for Dijkstra, BFS, or any 'shortest path' logic!
    """
    def dfs(current: int, target: int, parent: int) -> List[int]:
        if current == target:
            return [current]
        
        for neighbor in adj[current]:
            if neighbor != parent:
                path = dfs(neighbor, target, current)
                if path:
                    return [current] + path
        
        return []
    
    return dfs(u, v, -1)
 
def analyze_all_paths(n: int, edges: List[Tuple[int, int]]):
    """Analyze path statistics in a tree"""
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    all_distances = []
    
    for u in range(n):
        for v in range(u + 1, n):
            path = path_between(adj, u, v)
            distance = len(path) - 1  # Distance = edges = vertices - 1
            all_distances.append(distance)
    
    print(f"Number of unique paths: {len(all_distances)}")
    print(f"Expected (n choose 2): {n * (n-1) // 2}")
    print(f"Min path length: {min(all_distances)}")
    print(f"Max path length (diameter): {max(all_distances)}")
    print(f"Average path length: {sum(all_distances) / len(all_distances):.2f}")
 
# Example
edges = [(0, 1), (1, 2), (2, 3), (1, 4), (4, 5)]
analyze_all_paths(6, edges)

The Sum of All Distances:

A classic problem is computing the sum of distances between all pairs of vertices. For trees, this can be done in O(n) time using the contribution technique:

For each edge (u, v), count how many paths cross it:

Let nᵤ = vertices on u's side when edge removed
Let nᵥ = vertices on v's side = n - nᵤ
Edge (u, v) is crossed by nᵤ × nᵥ paths

Total sum = ∑ (nᵤ × nᵥ) over all edges

Summary: Tree Properties Through Graph Theory

We've explored fundamental tree properties through the rigorous lens of graph theory. These concepts appear across algorithms, competitive programming, and real-world applications. Let's consolidate:

Key Takeaways

•Eccentricity measures centrality — ecc(v) = max distance from v; low eccentricity = central, high = peripheral
•Diameter is the longest path — max{ d(u,v) }; computable in O(n) via two-BFS trick
•Radius is the minimum eccentricity — radius = ⌈diameter/2⌉
•Center has 1 or 2 vertices — lies at the midpoint of every diameter path
•Height depends on root choice — height when rooted at v = ecc(v); minimize by rooting at center
•Degree reveals structure — leaves have degree 1; sum of degrees = 2(n-1)
•Unique paths enable elegant algorithms — no need for 'shortest path' algorithms in trees

What's Next:

We'll extend these concepts by exploring forests—collections of disjoint trees. Understanding forests completes our picture of tree-graph relationships and prepares us for algorithms involving disconnected components.

Page Complete

You now understand fundamental tree properties in graph-theoretic terms. These metrics—diameter, radius, center, eccentricity—form the vocabulary of tree analysis across algorithms and applications. Next, we'll explore forests: multiple disconnected trees.