Tree Basics

A tree is a connected acyclic graph. It is a fundamental data structure in computer science and competitive programming.

Properties

• A tree with $n$ nodes has exactly $n-1$ edges.
• Any two nodes are connected by exactly one simple path.
• Removing any edge disconnects the tree.
• Adding any edge creates a cycle.

Terminology

• Root: The designated starting node of the tree (often node 0 or 1).
• Parent: The node directly above a given node.
• Child: A node directly below a given node.
• Leaf: A node with no children.
• Subtree: The tree formed by a node and all its descendants.
• Depth: The number of edges from the root to a node.
• Height: The maximum depth among all nodes.

Tree Traversal

Depth-First Search (DFS)

DFS is commonly used to traverse trees and compute properties such as subtree sizes, depths, and parents.

void dfs(int u, int p) {
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }
}

Breadth-First Search (BFS)

BFS can also be used to compute shortest paths from the root or any node.

void bfs(int root) {
    queue<int> q;
    q.push(root);
    vector<bool> visited(n, false);
    visited[root] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

Subtree Size

The size of the subtree rooted at each node can be computed using DFS:

vector<int> subtreeSize(n);

int dfs(int u, int p) {
    subtreeSize[u] = 1;
    for (int v : adj[u]) {
        if (v != p) {
            subtreeSize[u] += dfs(v, u);
        }
    }
    return subtreeSize[u];
}

Applications

• Finding the diameter of a tree
• Lowest Common Ancestor (LCA)
• Heavy-Light Decomposition (HLD)
• Centroid Decomposition
• Dynamic Programming on Trees

Trees are a core topic in algorithmic problem solving and are the basis for many advanced techniques.