Rooted vs Unrooted Trees — Trees as Special Graphs | OneNoughtOne

0/361

Data Structures & AlgorithmsGraphs

Trees as Special Graphs

LevelIntermediate

Duration60 mins

TopicGraphs

2 / 4

Rooted vs Unrooted Trees

The Root of All Understanding

When you first learned about trees in data structures, you probably started with the concept of a root —that special node at the top from which everything else descends. But here's a profound insight: in graph theory, trees don't have roots . They're just connected, acyclic graphs where no vertex is inherently 'special.' The root is something we choose to add. And that choice transforms an undirected, symmetric structure into a directed, hierarchical one. Understanding this distinction is crucial for appreciating both the mathematical foundations of trees and their practical implementations.

What You Will Learn

By the end of this page, you will understand the fundamental difference between rooted and unrooted trees, learn how choosing a root imposes direction and hierarchy, see how the same underlying graph can be rooted in multiple ways, and appreciate how this duality appears in algorithms and data structures.

Unrooted Trees: The Pure Graph-Theoretic Form

An unrooted tree is the natural graph-theoretic view of a tree: a connected, acyclic, undirected graph. In this view: All vertices are structurally equivalent in their role (though they may differ in degree) Edges have no inherent direction —they simply represent symmetric connections There is no hierarchy —no vertex is 'above' or 'below' another The tree looks the same no matter which vertex you start examining from Unrooted trees are common in several domains: Biology: Phylogenetic trees often start as unrooted, showing evolutionary relationships without assuming which species came first. Network Design: Physical network topologies (cables, connections) are inherently undirected—data can flow both ways. Graph Algorithms: Many algorithms process trees without caring about root position—they just need the connectivity structure.

Converting Mermaid diagram...

In the unrooted tree above, notice that no vertex is marked as special. We could redraw this with any vertex at the 'top' of our visualization, and it would represent the exact same tree. Vertices A, B, C, D, E, and F are all just connected nodes in a symmetric structure. Key Properties of Unrooted Trees: No parent-child relationships — Vertices are just neighbors Degree is the only structural distinction — Leaves have degree 1; internal nodes have degree > 1 Edges are bidirectional — Moving from A to B is the same as moving from B to A Any vertex can be a starting point — For traversals, algorithms, or analysis The structure is invariant to rotation/reflection — Only connectivity matters

Representation in Code

Unrooted trees are typically represented using adjacency lists where each edge appears twice (once for each direction), or as a set of undirected edges. There's no 'root' field, no 'parent' pointer—just neighbor relationships.

Rooted Trees: Imposing Hierarchy

A rooted tree is an unrooted tree with one distinguished vertex designated as the root . This single choice transforms the entire structure: Definition: A rooted tree is a tree in which one vertex is designated as the root, inducing a parent-child relationship on all edges, with edges directed away from the root toward the leaves. The moment you choose a root, several things happen automatically:

What Rooting a Tree Creates

•Parent-Child Relationships — Every non-root vertex has exactly one parent (its neighbor closer to the root)
•Levels/Depth — Each vertex is assigned a depth (distance from root). The root has depth 0.
•Ancestors and Descendants — Vertices on the path to the root are ancestors; vertices in the subtree are descendants
•Implicit Direction — Edges become directed from parent to child (or equivalently, child to parent)
•Subtree Structure — Each vertex becomes the root of its own subtree
•Leaf Definition Refinement — Leaves are now specifically vertices with no children (not just degree-1 vertices)

Converting Mermaid diagram...

The diagram above shows the same underlying tree rooted at two different vertices. Notice how: When rooted at A: B, E are children of A; C, D are children of B; F is child of E When rooted at B: A, C, D are children of B; E is child of A; F is child of E The connectivity is identical, but the hierarchical relationships are completely different. The choice of root is an additional piece of information on top of the graph structure.

The Root as a Perspective

Think of rooting a tree as choosing a 'viewpoint.' Just as looking at a 3D object from different angles gives different 2D projections, rooting a tree at different vertices gives different hierarchical structures—but the underlying graph is unchanged.

The Rooting Process: From Graph to Hierarchy

Let's formalize how we transform an unrooted tree into a rooted tree. This process is also called rooting a tree at vertex r . Algorithm: Root Tree at Vertex r Designate vertex r as the root (depth 0) For each neighbor v of r, make v a child of r (depth 1) Recursively: for each vertex at depth d, its unvisited neighbors become its children at depth d+1 Continue until all vertices are assigned a depth and parent

root_tree.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 Dict, List, Optional, Tuple
 
def root_tree(edges: List[Tuple[int, int]], root: int) -> Dict[int, List[int]]:
    """
    Convert an unrooted tree (given as edge list) into a rooted tree.
    
    Returns: Adjacency list where children[v] = list of v's children
    
    Key insight: In the unrooted tree, edges are bidirectional.
    Rooting assigns direction: parent → child (away from root).
    """
    # Build undirected adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # BFS/DFS from root to assign parent-child relationships
    children = defaultdict(list)
    parent = {root: None}  # Root has no parent
    
    def dfs(node: int, par: Optional[int]):
        """DFS to assign children based on rooting at 'root'"""
        for neighbor in adj[node]:
            if neighbor != par:  # Don't go back to parent
                parent[neighbor] = node
                children[node].append(neighbor)
                dfs(neighbor, node)
    
    dfs(root, None)
    return dict(children), parent
 
# Example: Root the same tree at different vertices
edges = [(0, 1), (1, 2), (1, 3), (0, 4), (4, 5)]
 
print("Tree rooted at 0:")
children, parent = root_tree(edges, 0)
for node in sorted(children.keys()):
    print(f"  {node}'s children: {children[node]}")
 
print("
Tree rooted at 1:")
children, parent = root_tree(edges, 1)
for node in sorted(children.keys()):
    print(f"  {node}'s children: {children[node]}")
 
# Output shows different hierarchies from the same graph!

Time Complexity: O(V + E) = O(V) since E = V - 1 for trees. Space Complexity: O(V) for the parent and children data structures. Key Implementation Details: Tracking visited vertices: We don't need a separate 'visited' set—instead, we pass the parent as a parameter and avoid going back to it. Building the children list: As we DFS from the root, every neighbor except the parent becomes a child. Storing parent pointers: Often useful for algorithms that need to traverse toward the root.

Terminology: Rooted vs Unrooted Context

When discussing trees, the same concepts often have different interpretations depending on whether we're in a rooted or unrooted context. Understanding these nuanced differences prevents confusion.

Terminology Comparison: Rooted vs Unrooted Trees
Term	Unrooted Tree	Rooted Tree
Leaf	Vertex with degree 1	Vertex with no children (may have degree 1 or be the root if tree has 1 node)
Internal Node	Vertex with degree > 1	Vertex with at least one child
Neighbor	Adjacent vertex (symmetric)	Parent or child (direction matters)
Path	Sequence of adjacent vertices	Often specific: root-to-node path has special significance
Distance	Number of edges on path between two vertices	Often: depth (distance from root) or height (max distance to leaf)
Subtree	Any connected subgraph that is a tree	All descendants of a vertex plus the vertex itself
Height	Maximum distance between any two vertices (diameter/2)	Maximum depth of any leaf in the subtree

Watch for Context

When reading about trees in textbooks, papers, or code comments, always determine whether the author is discussing rooted or unrooted trees. The term 'leaf' alone, for instance, can mean different things. In an unrooted tree, a degree-1 vertex is a leaf even if it becomes an internal node when rooted elsewhere.

Special Case: The Root in a Small Tree Consider a tree with just two vertices connected by one edge. In the unrooted view, both vertices have degree 1—both are 'leaves.' If we root this tree at vertex A: A is the root (no parent) B is the only child of A, and B is a leaf (no children) If we root at vertex B: B is the root A is the leaf Same graph, different hierarchies!

When Does the Choice of Root Matter?

Not all algorithms care about which vertex is the root—some only need the tree structure. Others are deeply affected by root choice. Understanding this distinction helps you design efficient solutions.

Root-Independent Operations

•Connectivity queries — Is there a path between u and v?
•Tree diameter — Longest path in the tree (same regardless of root)
•MST construction — Finding minimum spanning tree
•Edge existence — Checking if edge (u, v) exists
•Tree isomorphism — Structural equivalence of trees

Root-Dependent Operations

•LCA (Lowest Common Ancestor) — By definition, depends on root
•Subtree queries — 'Subtree of v' depends on root
•Depth/Level computations — Measured from root
•Tree DP with subtree aggregation — Often processes from leaves upward
•Ancestor/Descendant relationships — Depend on hierarchy

Choosing a Good Root: Some problems allow you to choose the root cleverly to simplify the algorithm: Root at the centroid: For balanced subtrees and efficient tree DP Root at a leaf: Simplifies some traversal logic Root at vertex 0 or 1: Common convention when any root works Root determined by problem: E.g., "node 1 is the company CEO" implies root Example: Tree DP Many tree DP problems compute values for each subtree (like sum, count, or max). These algorithms typically: Root the tree at an arbitrary vertex DFS from root, computing values bottom-up The root choice doesn't affect final answers for most problems—it just determines traversal order

tree_dp_example.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
def count_subtree_sizes(n: int, edges: list, root: int = 0) -> dict:
    """
    Count the size of each subtree when the tree is rooted at 'root'.
    
    This is a classic tree DP pattern:
    - Process children first (post-order)
    - Aggregate results at each node
    
    The answer depends on the root! Different roots give different subtree sizes.
    """
    from collections import defaultdict
    
    # Build adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    subtree_size = {}
    
    def dfs(node: int, parent: int) -> int:
        """Returns size of subtree rooted at 'node'"""
        size = 1  # Count this node
        for child in adj[node]:
            if child != parent:
                size += dfs(child, node)  # Add all children's subtree sizes
        subtree_size[node] = size
        return size
    
    dfs(root, -1)
    return subtree_size
 
# Example
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
#      0
#     / \
#    1   2
#   / \
#  3   4
 
print("Rooted at 0:", count_subtree_sizes(5, edges, 0))
# {3: 1, 4: 1, 1: 3, 2: 1, 0: 5}
# Node 1's subtree has 3 nodes (1, 3, 4)
 
print("Rooted at 1:", count_subtree_sizes(5, edges, 1))
# {3: 1, 4: 1, 2: 1, 0: 2, 1: 5}
# Now node 0's subtree has 2 nodes (0, 2)!

The Re-rooting Technique

A powerful technique in tree algorithms is re-rooting : computing an answer for every possible root efficiently. Naively, this would require O(n²) time (root at each of n vertices, O(n) per computation). The re-rooting technique achieves O(n) total. The Key Insight: When you 'move' the root from a vertex u to its neighbor v: V's subtree values stay mostly the same Only the relationship between u and v changes: v was u's child, now u becomes v's child We can update the answer incrementally rather than recomputing from scratch

Re-rooting Pattern

Re-rooting works in two phases: (1) Root at any vertex and compute 'down' values via DFS. (2) DFS again, computing 'up' values by considering what happens when the root moves to each child. This combines to give the answer for every root in O(n) time.

rerooting_sum_of_distances.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
def sum_of_distances_in_tree(n: int, edges: list) -> list:
    """
    For each node, compute sum of distances to all other nodes.
    
    Naive approach: BFS from each node = O(n²)
    Re-rooting approach: O(n) total
    
    When we move root from u to v (where v is u's child):
    - Nodes in v's subtree get 1 closer
    - All other nodes get 1 farther
    - answer[v] = answer[u] - subtree_size[v] + (n - subtree_size[v])
    """
    from collections import defaultdict
    
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    subtree_size = [1] * n
    dist_sum = [0] * n  # dist_sum[i] = sum of distances from i to all nodes in i's subtree
    
    # Phase 1: Root at 0, compute subtree sizes and subtree distance sums
    def dfs1(node: int, parent: int) -> None:
        for child in adj[node]:
            if child != parent:
                dfs1(child, node)
                subtree_size[node] += subtree_size[child]
                # Distance to all nodes in child's subtree = their internal distances + 1 each
                dist_sum[node] += dist_sum[child] + subtree_size[child]
    
    dfs1(0, -1)
    
    # Phase 2: Re-root to compute answer for all nodes
    answer = [0] * n
    answer[0] = dist_sum[0]  # Answer for root is just its subtree distance sum
    
    def dfs2(node: int, parent: int) -> None:
        for child in adj[node]:
            if child != parent:
                # Moving root from 'node' to 'child':
                # - subtree_size[child] nodes get 1 closer
                # - (n - subtree_size[child]) nodes get 1 farther
                answer[child] = answer[node] - subtree_size[child] + (n - subtree_size[child])
                dfs2(child, node)
    
    dfs2(0, -1)
    return answer
 
# Example
edges = [(0, 1), (0, 2), (2, 3), (2, 4), (2, 5)]
result = sum_of_distances_in_tree(6, edges)
print(f"Sum of distances for each node: {result}")
# answer[i] = sum of distances from i to all other nodes

The re-rooting technique is a beautiful example of how understanding the relationship between rooted and unrooted views leads to efficient algorithms. By leveraging the incremental change when moving the root, we avoid redundant computation.

Data Structure Representations

In practice, rooted and unrooted trees are represented differently in code, reflecting their structural differences.

Common Representations
Representation	Best For	Example
Edge List	Unrooted trees, input parsing	[(0,1), (1,2), (0,3)]
Adjacency List (undirected)	Unrooted trees, traversals	{0: [1,3], 1: [0,2], 2: [1], 3: [0]}
Children List	Rooted trees (from known root)	{0: [1,3], 1: [2], 2: [], 3: []}
Parent Array	Rooted trees, LCA queries	parent = [-1, 0, 1, 0] (root has -1)
Node Objects with parent/children	OOP tree structures	class Node: parent, children, val
Binary tree arrays	Complete binary trees (heaps)	[root, left, right, ...]

representations.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
84
from typing import List, Dict, Optional
from collections import defaultdict
from dataclasses import dataclass, field
 
# ===============================
# UNROOTED TREE REPRESENTATIONS
# ===============================
 
# 1. Edge List - Simple, common for input
edges_list = [(0, 1), (1, 2), (1, 3), (0, 4)]
 
# 2. Adjacency List - Standard for traversals
def edges_to_adj_list(edges: List[tuple]) -> Dict[int, List[int]]:
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)  # Undirected: add both directions
    return dict(adj)
 
# ===============================
# ROOTED TREE REPRESENTATIONS
# ===============================
 
# 3. Children list - When you have a specific root
def build_children_list(edges: List[tuple], root: int) -> Dict[int, List[int]]:
    adj = edges_to_adj_list(edges)
    children = defaultdict(list)
    visited = {root}
    
    def dfs(node):
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                children[node].append(neighbor)
                dfs(neighbor)
    
    dfs(root)
    return dict(children)
 
# 4. Parent array - Compact, good for LCA
def build_parent_array(edges: List[tuple], root: int, n: int) -> List[int]:
    adj = edges_to_adj_list(edges)
    parent = [-1] * n  # -1 indicates no parent (root)
    visited = {root}
    
    def dfs(node):
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                dfs(neighbor)
    
    dfs(root)
    return parent
 
# 5. Node objects - OOP style
@dataclass
class TreeNode:
    val: int
    parent: Optional['TreeNode'] = None
    children: List['TreeNode'] = field(default_factory=list)
 
def build_tree_objects(edges: List[tuple], root: int) -> TreeNode:
    nodes = {i: TreeNode(val=i) for i in range(len(edges) + 1)}
    adj = edges_to_adj_list(edges)
    visited = {root}
    
    def dfs(node_id: int, parent_id: Optional[int]):
        if parent_id is not None:
            nodes[node_id].parent = nodes[parent_id]
        for neighbor in adj[node_id]:
            if neighbor not in visited:
                visited.add(neighbor)
                nodes[node_id].children.append(nodes[neighbor])
                dfs(neighbor, node_id)
    
    dfs(root, None)
    return nodes[root]
 
# Example usage
edges = [(0, 1), (1, 2), (1, 3), (0, 4)]
print("Adjacency list:", edges_to_adj_list(edges))
print("Children (root=0):", build_children_list(edges, 0))
print("Parent array (root=0):", build_parent_array(edges, 0, 5))

Data Structures & AlgorithmsGraphs

Trees as Special Graphs

LevelIntermediate

Duration60 mins

TopicGraphs

2 / 4

Rooted vs Unrooted Trees

The Root of All Understanding

When you first learned about trees in data structures, you probably started with the concept of a root —that special node at the top from which everything else descends. But here's a profound insight: in graph theory, trees don't have roots . They're just connected, acyclic graphs where no vertex is inherently 'special.' The root is something we choose to add. And that choice transforms an undirected, symmetric structure into a directed, hierarchical one. Understanding this distinction is crucial for appreciating both the mathematical foundations of trees and their practical implementations.

What You Will Learn

By the end of this page, you will understand the fundamental difference between rooted and unrooted trees, learn how choosing a root imposes direction and hierarchy, see how the same underlying graph can be rooted in multiple ways, and appreciate how this duality appears in algorithms and data structures.

Unrooted Trees: The Pure Graph-Theoretic Form

An unrooted tree is the natural graph-theoretic view of a tree: a connected, acyclic, undirected graph. In this view: All vertices are structurally equivalent in their role (though they may differ in degree) Edges have no inherent direction —they simply represent symmetric connections There is no hierarchy —no vertex is 'above' or 'below' another The tree looks the same no matter which vertex you start examining from Unrooted trees are common in several domains: Biology: Phylogenetic trees often start as unrooted, showing evolutionary relationships without assuming which species came first. Network Design: Physical network topologies (cables, connections) are inherently undirected—data can flow both ways. Graph Algorithms: Many algorithms process trees without caring about root position—they just need the connectivity structure.

Converting Mermaid diagram...

In the unrooted tree above, notice that no vertex is marked as special. We could redraw this with any vertex at the 'top' of our visualization, and it would represent the exact same tree. Vertices A, B, C, D, E, and F are all just connected nodes in a symmetric structure. Key Properties of Unrooted Trees: No parent-child relationships — Vertices are just neighbors Degree is the only structural distinction — Leaves have degree 1; internal nodes have degree > 1 Edges are bidirectional — Moving from A to B is the same as moving from B to A Any vertex can be a starting point — For traversals, algorithms, or analysis The structure is invariant to rotation/reflection — Only connectivity matters

Representation in Code

Unrooted trees are typically represented using adjacency lists where each edge appears twice (once for each direction), or as a set of undirected edges. There's no 'root' field, no 'parent' pointer—just neighbor relationships.

Rooted Trees: Imposing Hierarchy

A rooted tree is an unrooted tree with one distinguished vertex designated as the root . This single choice transforms the entire structure: Definition: A rooted tree is a tree in which one vertex is designated as the root, inducing a parent-child relationship on all edges, with edges directed away from the root toward the leaves. The moment you choose a root, several things happen automatically:

What Rooting a Tree Creates

•Parent-Child Relationships — Every non-root vertex has exactly one parent (its neighbor closer to the root)
•Levels/Depth — Each vertex is assigned a depth (distance from root). The root has depth 0.
•Ancestors and Descendants — Vertices on the path to the root are ancestors; vertices in the subtree are descendants
•Implicit Direction — Edges become directed from parent to child (or equivalently, child to parent)
•Subtree Structure — Each vertex becomes the root of its own subtree
•Leaf Definition Refinement — Leaves are now specifically vertices with no children (not just degree-1 vertices)

Converting Mermaid diagram...

The diagram above shows the same underlying tree rooted at two different vertices. Notice how: When rooted at A: B, E are children of A; C, D are children of B; F is child of E When rooted at B: A, C, D are children of B; E is child of A; F is child of E The connectivity is identical, but the hierarchical relationships are completely different. The choice of root is an additional piece of information on top of the graph structure.

The Root as a Perspective

Think of rooting a tree as choosing a 'viewpoint.' Just as looking at a 3D object from different angles gives different 2D projections, rooting a tree at different vertices gives different hierarchical structures—but the underlying graph is unchanged.

The Rooting Process: From Graph to Hierarchy

Let's formalize how we transform an unrooted tree into a rooted tree. This process is also called rooting a tree at vertex r . Algorithm: Root Tree at Vertex r Designate vertex r as the root (depth 0) For each neighbor v of r, make v a child of r (depth 1) Recursively: for each vertex at depth d, its unvisited neighbors become its children at depth d+1 Continue until all vertices are assigned a depth and parent

root_tree.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 Dict, List, Optional, Tuple
 
def root_tree(edges: List[Tuple[int, int]], root: int) -> Dict[int, List[int]]:
    """
    Convert an unrooted tree (given as edge list) into a rooted tree.
    
    Returns: Adjacency list where children[v] = list of v's children
    
    Key insight: In the unrooted tree, edges are bidirectional.
    Rooting assigns direction: parent → child (away from root).
    """
    # Build undirected adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # BFS/DFS from root to assign parent-child relationships
    children = defaultdict(list)
    parent = {root: None}  # Root has no parent
    
    def dfs(node: int, par: Optional[int]):
        """DFS to assign children based on rooting at 'root'"""
        for neighbor in adj[node]:
            if neighbor != par:  # Don't go back to parent
                parent[neighbor] = node
                children[node].append(neighbor)
                dfs(neighbor, node)
    
    dfs(root, None)
    return dict(children), parent
 
# Example: Root the same tree at different vertices
edges = [(0, 1), (1, 2), (1, 3), (0, 4), (4, 5)]
 
print("Tree rooted at 0:")
children, parent = root_tree(edges, 0)
for node in sorted(children.keys()):
    print(f"  {node}'s children: {children[node]}")
 
print("
Tree rooted at 1:")
children, parent = root_tree(edges, 1)
for node in sorted(children.keys()):
    print(f"  {node}'s children: {children[node]}")
 
# Output shows different hierarchies from the same graph!

Time Complexity: O(V + E) = O(V) since E = V - 1 for trees. Space Complexity: O(V) for the parent and children data structures. Key Implementation Details: Tracking visited vertices: We don't need a separate 'visited' set—instead, we pass the parent as a parameter and avoid going back to it. Building the children list: As we DFS from the root, every neighbor except the parent becomes a child. Storing parent pointers: Often useful for algorithms that need to traverse toward the root.

Terminology: Rooted vs Unrooted Context

When discussing trees, the same concepts often have different interpretations depending on whether we're in a rooted or unrooted context. Understanding these nuanced differences prevents confusion.

Terminology Comparison: Rooted vs Unrooted Trees
Term	Unrooted Tree	Rooted Tree
Leaf	Vertex with degree 1	Vertex with no children (may have degree 1 or be the root if tree has 1 node)
Internal Node	Vertex with degree > 1	Vertex with at least one child
Neighbor	Adjacent vertex (symmetric)	Parent or child (direction matters)
Path	Sequence of adjacent vertices	Often specific: root-to-node path has special significance
Distance	Number of edges on path between two vertices	Often: depth (distance from root) or height (max distance to leaf)
Subtree	Any connected subgraph that is a tree	All descendants of a vertex plus the vertex itself
Height	Maximum distance between any two vertices (diameter/2)	Maximum depth of any leaf in the subtree

Watch for Context

When reading about trees in textbooks, papers, or code comments, always determine whether the author is discussing rooted or unrooted trees. The term 'leaf' alone, for instance, can mean different things. In an unrooted tree, a degree-1 vertex is a leaf even if it becomes an internal node when rooted elsewhere.

Special Case: The Root in a Small Tree Consider a tree with just two vertices connected by one edge. In the unrooted view, both vertices have degree 1—both are 'leaves.' If we root this tree at vertex A: A is the root (no parent) B is the only child of A, and B is a leaf (no children) If we root at vertex B: B is the root A is the leaf Same graph, different hierarchies!

When Does the Choice of Root Matter?

Not all algorithms care about which vertex is the root—some only need the tree structure. Others are deeply affected by root choice. Understanding this distinction helps you design efficient solutions.

Root-Independent Operations

•Connectivity queries — Is there a path between u and v?
•Tree diameter — Longest path in the tree (same regardless of root)
•MST construction — Finding minimum spanning tree
•Edge existence — Checking if edge (u, v) exists
•Tree isomorphism — Structural equivalence of trees

Root-Dependent Operations

•LCA (Lowest Common Ancestor) — By definition, depends on root
•Subtree queries — 'Subtree of v' depends on root
•Depth/Level computations — Measured from root
•Tree DP with subtree aggregation — Often processes from leaves upward
•Ancestor/Descendant relationships — Depend on hierarchy

Choosing a Good Root: Some problems allow you to choose the root cleverly to simplify the algorithm: Root at the centroid: For balanced subtrees and efficient tree DP Root at a leaf: Simplifies some traversal logic Root at vertex 0 or 1: Common convention when any root works Root determined by problem: E.g., "node 1 is the company CEO" implies root Example: Tree DP Many tree DP problems compute values for each subtree (like sum, count, or max). These algorithms typically: Root the tree at an arbitrary vertex DFS from root, computing values bottom-up The root choice doesn't affect final answers for most problems—it just determines traversal order

tree_dp_example.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
def count_subtree_sizes(n: int, edges: list, root: int = 0) -> dict:
    """
    Count the size of each subtree when the tree is rooted at 'root'.
    
    This is a classic tree DP pattern:
    - Process children first (post-order)
    - Aggregate results at each node
    
    The answer depends on the root! Different roots give different subtree sizes.
    """
    from collections import defaultdict
    
    # Build adjacency list
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    subtree_size = {}
    
    def dfs(node: int, parent: int) -> int:
        """Returns size of subtree rooted at 'node'"""
        size = 1  # Count this node
        for child in adj[node]:
            if child != parent:
                size += dfs(child, node)  # Add all children's subtree sizes
        subtree_size[node] = size
        return size
    
    dfs(root, -1)
    return subtree_size
 
# Example
edges = [(0, 1), (0, 2), (1, 3), (1, 4)]
#      0
#     / \
#    1   2
#   / \
#  3   4
 
print("Rooted at 0:", count_subtree_sizes(5, edges, 0))
# {3: 1, 4: 1, 1: 3, 2: 1, 0: 5}
# Node 1's subtree has 3 nodes (1, 3, 4)
 
print("Rooted at 1:", count_subtree_sizes(5, edges, 1))
# {3: 1, 4: 1, 2: 1, 0: 2, 1: 5}
# Now node 0's subtree has 2 nodes (0, 2)!

The Re-rooting Technique

A powerful technique in tree algorithms is re-rooting : computing an answer for every possible root efficiently. Naively, this would require O(n²) time (root at each of n vertices, O(n) per computation). The re-rooting technique achieves O(n) total. The Key Insight: When you 'move' the root from a vertex u to its neighbor v: V's subtree values stay mostly the same Only the relationship between u and v changes: v was u's child, now u becomes v's child We can update the answer incrementally rather than recomputing from scratch

Re-rooting Pattern

Re-rooting works in two phases: (1) Root at any vertex and compute 'down' values via DFS. (2) DFS again, computing 'up' values by considering what happens when the root moves to each child. This combines to give the answer for every root in O(n) time.

rerooting_sum_of_distances.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
def sum_of_distances_in_tree(n: int, edges: list) -> list:
    """
    For each node, compute sum of distances to all other nodes.
    
    Naive approach: BFS from each node = O(n²)
    Re-rooting approach: O(n) total
    
    When we move root from u to v (where v is u's child):
    - Nodes in v's subtree get 1 closer
    - All other nodes get 1 farther
    - answer[v] = answer[u] - subtree_size[v] + (n - subtree_size[v])
    """
    from collections import defaultdict
    
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    subtree_size = [1] * n
    dist_sum = [0] * n  # dist_sum[i] = sum of distances from i to all nodes in i's subtree
    
    # Phase 1: Root at 0, compute subtree sizes and subtree distance sums
    def dfs1(node: int, parent: int) -> None:
        for child in adj[node]:
            if child != parent:
                dfs1(child, node)
                subtree_size[node] += subtree_size[child]
                # Distance to all nodes in child's subtree = their internal distances + 1 each
                dist_sum[node] += dist_sum[child] + subtree_size[child]
    
    dfs1(0, -1)
    
    # Phase 2: Re-root to compute answer for all nodes
    answer = [0] * n
    answer[0] = dist_sum[0]  # Answer for root is just its subtree distance sum
    
    def dfs2(node: int, parent: int) -> None:
        for child in adj[node]:
            if child != parent:
                # Moving root from 'node' to 'child':
                # - subtree_size[child] nodes get 1 closer
                # - (n - subtree_size[child]) nodes get 1 farther
                answer[child] = answer[node] - subtree_size[child] + (n - subtree_size[child])
                dfs2(child, node)
    
    dfs2(0, -1)
    return answer
 
# Example
edges = [(0, 1), (0, 2), (2, 3), (2, 4), (2, 5)]
result = sum_of_distances_in_tree(6, edges)
print(f"Sum of distances for each node: {result}")
# answer[i] = sum of distances from i to all other nodes

The re-rooting technique is a beautiful example of how understanding the relationship between rooted and unrooted views leads to efficient algorithms. By leveraging the incremental change when moving the root, we avoid redundant computation.

Data Structure Representations

In practice, rooted and unrooted trees are represented differently in code, reflecting their structural differences.

Common Representations
Representation	Best For	Example
Edge List	Unrooted trees, input parsing	[(0,1), (1,2), (0,3)]
Adjacency List (undirected)	Unrooted trees, traversals	{0: [1,3], 1: [0,2], 2: [1], 3: [0]}
Children List	Rooted trees (from known root)	{0: [1,3], 1: [2], 2: [], 3: []}
Parent Array	Rooted trees, LCA queries	parent = [-1, 0, 1, 0] (root has -1)
Node Objects with parent/children	OOP tree structures	class Node: parent, children, val
Binary tree arrays	Complete binary trees (heaps)	[root, left, right, ...]

representations.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
84
from typing import List, Dict, Optional
from collections import defaultdict
from dataclasses import dataclass, field
 
# ===============================
# UNROOTED TREE REPRESENTATIONS
# ===============================
 
# 1. Edge List - Simple, common for input
edges_list = [(0, 1), (1, 2), (1, 3), (0, 4)]
 
# 2. Adjacency List - Standard for traversals
def edges_to_adj_list(edges: List[tuple]) -> Dict[int, List[int]]:
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)  # Undirected: add both directions
    return dict(adj)
 
# ===============================
# ROOTED TREE REPRESENTATIONS
# ===============================
 
# 3. Children list - When you have a specific root
def build_children_list(edges: List[tuple], root: int) -> Dict[int, List[int]]:
    adj = edges_to_adj_list(edges)
    children = defaultdict(list)
    visited = {root}
    
    def dfs(node):
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                children[node].append(neighbor)
                dfs(neighbor)
    
    dfs(root)
    return dict(children)
 
# 4. Parent array - Compact, good for LCA
def build_parent_array(edges: List[tuple], root: int, n: int) -> List[int]:
    adj = edges_to_adj_list(edges)
    parent = [-1] * n  # -1 indicates no parent (root)
    visited = {root}
    
    def dfs(node):
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                dfs(neighbor)
    
    dfs(root)
    return parent
 
# 5. Node objects - OOP style
@dataclass
class TreeNode:
    val: int
    parent: Optional['TreeNode'] = None
    children: List['TreeNode'] = field(default_factory=list)
 
def build_tree_objects(edges: List[tuple], root: int) -> TreeNode:
    nodes = {i: TreeNode(val=i) for i in range(len(edges) + 1)}
    adj = edges_to_adj_list(edges)
    visited = {root}
    
    def dfs(node_id: int, parent_id: Optional[int]):
        if parent_id is not None:
            nodes[node_id].parent = nodes[parent_id]
        for neighbor in adj[node_id]:
            if neighbor not in visited:
                visited.add(neighbor)
                nodes[node_id].children.append(nodes[neighbor])
                dfs(neighbor, node_id)
    
    dfs(root, None)
    return nodes[root]
 
# Example usage
edges = [(0, 1), (1, 2), (1, 3), (0, 4)]
print("Adjacency list:", edges_to_adj_list(edges))
print("Children (root=0):", build_children_list(edges, 0))
print("Parent array (root=0):", build_parent_array(edges, 0, 5))

Rooted vs Unrooted Trees

The Root of All Understanding

Unrooted Trees: The Pure Graph-Theoretic Form

Rooted Trees: Imposing Hierarchy

The Rooting Process: From Graph to Hierarchy

Terminology: Rooted vs Unrooted Context

When Does the Choice of Root Matter?

The Re-rooting Technique

Data Structure Representations

There’s more to understand.

Rooted vs Unrooted Trees

The Root of All Understanding

Unrooted Trees: The Pure Graph-Theoretic Form

Rooted Trees: Imposing Hierarchy

The Rooting Process: From Graph to Hierarchy

Terminology: Rooted vs Unrooted Context

When Does the Choice of Root Matter?

The Re-rooting Technique

Data Structure Representations

There’s more to understand.