Chapter 24 of 30

Rooted Trees — DFS, Subtree Size & Diameter

Master tree terminology, rooting, subtree sizes, tree diameter, and distance calculations for competitive programming.

Tree TerminologyRooting a TreeTree DiameterDistance Between Two VerticesTree Algorithms: Summary of Techniques

Rooted Trees — DFS, Subtree Size & Diameter

Trees are graphs with no cycles. They're one of the most important structures in competitive programming — appearing in problems about hierarchies, organization charts, file systems, and more.

Tree Terminology

Root: the designated top node (usually node 0 or 1)
Parent: the node above in the hierarchy
Children: nodes directly below
Leaf: a node with no children
Subtree: a node and all its descendants
Depth: distance from root (root has depth 0)
Height: maximum depth of any node in the subtree

Rooting a Tree

Any undirected tree can be rooted at any node. To root at node 0:

hljs cpp

vector<vector<int>> adj(n);

// Build rooted tree with parent tracking
vector<int> parent(n, -1);
vector<vector<int>> children(n);

function<void(int, int)> dfs = [&](int u, int p) {
    parent[u] = p;
    for (int v : adj[u]) {
        if (v != p) {
            children[u].push_back(v);
            dfs(v, u);
        }
    }
};

dfs(0, -1);

Subtree Size

hljs cpp

vector<int> subtreeSize(n, 1);

function<void(int, int)> dfs = [&](int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            subtreeSize[u] += subtreeSize[v];
        }
    }
};

dfs(0, -1);
// subtreeSize[u] = number of nodes in u's subtree

Tree Diameter

The diameter is the longest path between any two nodes in the tree.

Two-BFS/DFS Method

BFS/DFS from any node to find the farthest node a
BFS/DFS from a to find the farthest node b
Distance from a to b is the diameter

hljs cpp

pair<int, int> bfs(int start) {
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    int farthest = start;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[farthest]) farthest = v;
            }
        }
    }
    return {farthest, dist[farthest]};
}

auto [a, _] = bfs(0);
auto [b, diameter] = bfs(a);

DFS Method

hljs cpp

int diameter = 0;

// Returns the height of the subtree
function<int(int, int)> dfs = [&](int u, int p) {
    int maxDepth1 = 0, maxDepth2 = 0;
    for (int v : adj[u]) {
        if (v != p) {
            int depth = dfs(v, u) + 1;
            if (depth > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = depth;
            } else if (depth > maxDepth2) {
                maxDepth2 = depth;
            }
        }
    }
    diameter = max(diameter, maxDepth1 + maxDepth2);
    return maxDepth1;
};

dfs(0, -1);

Distance Between Two Vertices

Using LCA (covered in the next chapter):

code

dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]

Without LCA, BFS from u gives distances to all nodes.

Tree Algorithms: Summary of Techniques

Technique	What It Finds
DFS from root	Depth, parent, subtree sizes
Two BFS/DFS	Diameter
DFS with return values	Height, diameter, max path
LCA	Distance between nodes
DP on trees	Maximum independent set, coloring
centroid decomposition	Path queries on trees

Maximum Independent Set on a Tree

hljs cpp

// dp[u][0] = max weight in u's subtree, u NOT selected
// dp[u][1] = max weight in u's subtree, u selected
vector<vector<long long>> dp(n, vector<long long>(2));

function<void(int, int)> dfs = [&](int u, int p) {
    dp[u][1] = weight[u];
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
};

dfs(0, -1);
long long answer = max(dp[0][0], dp[0][1]);

Summary

Root any node to create a rooted tree; track parent and children
Subtree size: DFS returns size, parent accumulates children's sizes
Diameter: two BFS/DFS passes or single DFS tracking top-2 depths
Tree DP: dp[u] depends on dp[children] — process in DFS order
Trees have n-1 edges, so DFS/BFS is O(n)

Ch 23: Dijkstra, 0-1 BFS & Kruskal's MST Ch 25: Binary Lifting, LCA & Euler Tour

Prefer reading offline? Download the full book as a PDF.

Download Free Book

Chapter 24 of 30

Rooted Trees — DFS, Subtree Size & Diameter

Master tree terminology, rooting, subtree sizes, tree diameter, and distance calculations for competitive programming.

Tree TerminologyRooting a TreeTree DiameterDistance Between Two VerticesTree Algorithms: Summary of Techniques

Rooted Trees — DFS, Subtree Size & Diameter

Trees are graphs with no cycles. They're one of the most important structures in competitive programming — appearing in problems about hierarchies, organization charts, file systems, and more.

Tree Terminology

Root: the designated top node (usually node 0 or 1)
Parent: the node above in the hierarchy
Children: nodes directly below
Leaf: a node with no children
Subtree: a node and all its descendants
Depth: distance from root (root has depth 0)
Height: maximum depth of any node in the subtree

Rooting a Tree

Any undirected tree can be rooted at any node. To root at node 0:

hljs cpp

vector<vector<int>> adj(n);

// Build rooted tree with parent tracking
vector<int> parent(n, -1);
vector<vector<int>> children(n);

function<void(int, int)> dfs = [&](int u, int p) {
    parent[u] = p;
    for (int v : adj[u]) {
        if (v != p) {
            children[u].push_back(v);
            dfs(v, u);
        }
    }
};

dfs(0, -1);

Subtree Size

hljs cpp

vector<int> subtreeSize(n, 1);

function<void(int, int)> dfs = [&](int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            subtreeSize[u] += subtreeSize[v];
        }
    }
};

dfs(0, -1);
// subtreeSize[u] = number of nodes in u's subtree

Tree Diameter

The diameter is the longest path between any two nodes in the tree.

Two-BFS/DFS Method

BFS/DFS from any node to find the farthest node a
BFS/DFS from a to find the farthest node b
Distance from a to b is the diameter

hljs cpp

pair<int, int> bfs(int start) {
    vector<int> dist(n, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    int farthest = start;
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
                if (dist[v] > dist[farthest]) farthest = v;
            }
        }
    }
    return {farthest, dist[farthest]};
}

auto [a, _] = bfs(0);
auto [b, diameter] = bfs(a);

DFS Method

hljs cpp

int diameter = 0;

// Returns the height of the subtree
function<int(int, int)> dfs = [&](int u, int p) {
    int maxDepth1 = 0, maxDepth2 = 0;
    for (int v : adj[u]) {
        if (v != p) {
            int depth = dfs(v, u) + 1;
            if (depth > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = depth;
            } else if (depth > maxDepth2) {
                maxDepth2 = depth;
            }
        }
    }
    diameter = max(diameter, maxDepth1 + maxDepth2);
    return maxDepth1;
};

dfs(0, -1);

Distance Between Two Vertices

Using LCA (covered in the next chapter):

code

dist(u, v) = depth[u] + depth[v] - 2 * depth[lca(u, v)]

Without LCA, BFS from u gives distances to all nodes.

Tree Algorithms: Summary of Techniques

Technique	What It Finds
DFS from root	Depth, parent, subtree sizes
Two BFS/DFS	Diameter
DFS with return values	Height, diameter, max path
LCA	Distance between nodes
DP on trees	Maximum independent set, coloring
centroid decomposition	Path queries on trees

Maximum Independent Set on a Tree

hljs cpp

// dp[u][0] = max weight in u's subtree, u NOT selected
// dp[u][1] = max weight in u's subtree, u selected
vector<vector<long long>> dp(n, vector<long long>(2));

function<void(int, int)> dfs = [&](int u, int p) {
    dp[u][1] = weight[u];
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            dp[u][0] += max(dp[v][0], dp[v][1]);
            dp[u][1] += dp[v][0];
        }
    }
};

dfs(0, -1);
long long answer = max(dp[0][0], dp[0][1]);

Summary

Root any node to create a rooted tree; track parent and children
Subtree size: DFS returns size, parent accumulates children's sizes
Diameter: two BFS/DFS passes or single DFS tracking top-2 depths
Tree DP: dp[u] depends on dp[children] — process in DFS order
Trees have n-1 edges, so DFS/BFS is O(n)

Ch 23: Dijkstra, 0-1 BFS & Kruskal's MST Ch 25: Binary Lifting, LCA & Euler Tour

Prefer reading offline? Download the full book as a PDF.

Download Free Book