> ## Documentation Index
> Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt
> Use this file to discover all available pages before exploring further.

# Tree Algorithms

> Master tree traversals, LCA, tree DP, and hierarchical structures

# Tree Algorithms

## Why Trees Matter

Trees appear everywhere in CP: organizational hierarchies, file systems, game trees, and as subproblems in graph algorithms. A tree with n nodes has exactly n-1 edges and a unique path between any two nodes.

**Analogy**: A tree is a family genealogy chart. There is one ancestor at the top (the root), each person has exactly one parent (except the root), and there are no marriages within the family (no cycles). The unique path between any two people goes up to their lowest common ancestor, then down.

**Key properties to internalize**:

* n nodes, n-1 edges, always connected, no cycles
* Removing any edge splits the tree into exactly two components
* Adding any edge creates exactly one cycle
* The path between any two nodes is unique

<Note>
  **Pattern Recognition Signals**:

  * "n nodes, n-1 edges" → It's a tree
  * "Unique path between nodes" → Tree path queries
  * "Subtree sum/count" → DFS + subtree aggregation
  * "Path from u to v" → LCA + path decomposition
  * "Root the tree at node 1" → DFS from root
</Note>

***

## Tree Representations

```cpp theme={null}
// Most common: Adjacency list (unrooted tree)
int n;
vector<vector<int>> adj(n + 1);

for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Rooted tree: Store parent and children
vector<int> parent(n + 1);
vector<vector<int>> children(n + 1);

void root(int u, int p) {
    parent[u] = p;
    for (int v : adj[u]) {
        if (v != p) {
            children[u].push_back(v);
            root(v, u);
        }
    }
}
```

***

## DFS on Trees

### Basic Template

```cpp theme={null}
vector<int> subtreeSize(n + 1);
vector<int> depth(n + 1);

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

// Start DFS from root
depth[1] = 0;
dfs(1, 0);
```

### Euler Tour (Flatten Tree to Array)

Converts tree to array for range queries on subtrees. This is one of the most important techniques in tree problems.

**The Insight**: When you run DFS, you visit each node's subtree contiguously. If you record the entry time `tin[u]` and exit time `tout[u]`, then the subtree of u occupies a contiguous range `[tin[u], tout[u])` in the Euler order. This means you can answer subtree queries (sum, min, max of values in u's subtree) using a segment tree or BIT over the flattened array.

**Visual Example** for tree with root 1, children 2 and 3, where 2 has children 4 and 5:

```
Tree:     1
         / \
        2   3
       / \
      4   5

Euler tour: [1, 2, 4, 5, 3]
tin:    1→0, 2→1, 4→2, 5→3, 3→4
tout:   1→5, 2→4, 4→3, 5→4, 3→5

Subtree of 2 = euler[1..3] = [2, 4, 5]  (correct!)
Subtree of 1 = euler[0..4] = [1, 2, 4, 5, 3] (entire tree)
```

```cpp theme={null}
vector<int> tin(n + 1), tout(n + 1);
vector<int> euler;   // Nodes in DFS order
int timer = 0;

void eulerTour(int u, int p) {
    tin[u] = timer++;       // Record entry time
    euler.push_back(u);
    
    for (int v : adj[u]) {
        if (v != p) {
            eulerTour(v, u);
        }
    }
    
    tout[u] = timer;  // tout[u] = tin[u] + subtreeSize[u]
}

// Subtree of u corresponds to euler[tin[u]...tout[u]-1]
// To query subtree sum: segTree.query(tin[u], tout[u] - 1)
```

**Application**: Range queries on subtrees using segment trees. Update a node's value at position `tin[u]` in the segment tree, and query subtree sums over `[tin[u], tout[u]-1]`.

***

## Pattern 1: Tree Diameter

**Problem**: Find the longest path in a tree. The tree diameter is the number of edges on the longest path between any two nodes.

**Why the double-BFS trick works**: Starting from any node, the farthest node from it must be an endpoint of some diameter. This is provable by contradiction: if the farthest node were not a diameter endpoint, there would exist a longer path, contradicting that our node was farthest. So BFS from any start gives one diameter endpoint, and BFS from that endpoint gives the other.

### Two BFS/DFS Method

```cpp theme={null}
pair<int, int> bfs(int start) {  // Returns {farthest node, distance}
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;
    
    int farthest = start, maxDist = 0;
    
    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] > maxDist) {
                    maxDist = dist[v];
                    farthest = v;
                }
            }
        }
    }
    
    return {farthest, maxDist};
}

int treeDiameter() {
    auto [u, _] = bfs(1);      // Find one endpoint
    auto [v, diameter] = bfs(u);  // Find other endpoint
    return diameter;
}
```

### DP Method (Also Returns Path)

```cpp theme={null}
int diameter = 0;
int diameterEndpoint;

int dfs(int u, int p) {
    int maxDepth1 = 0, maxDepth2 = 0;
    
    for (int v : adj[u]) {
        if (v != p) {
            int childDepth = dfs(v, u) + 1;
            
            if (childDepth > maxDepth1) {
                maxDepth2 = maxDepth1;
                maxDepth1 = childDepth;
            } else if (childDepth > maxDepth2) {
                maxDepth2 = childDepth;
            }
        }
    }
    
    if (maxDepth1 + maxDepth2 > diameter) {
        diameter = maxDepth1 + maxDepth2;
    }
    
    return maxDepth1;
}
```

***

## Pattern 2: Lowest Common Ancestor (LCA)

**Problem**: Find the lowest common ancestor of two nodes.

### Binary Lifting

Precompute ancestors at powers of 2 for O(log n) queries.

```cpp theme={null}
const int LOG = 20;
vector<vector<int>> up(n + 1, vector<int>(LOG));
vector<int> depth(n + 1);

void preprocess(int root) {
    // BFS to compute depth and first ancestor
    queue<int> q;
    q.push(root);
    depth[root] = 0;
    up[root][0] = root;  // Parent of root is itself
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (depth[v] == 0 && v != root) {
                depth[v] = depth[u] + 1;
                up[v][0] = u;
                q.push(v);
            }
        }
    }
    
    // Build sparse table
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
    // Make u the deeper node
    if (depth[u] < depth[v]) swap(u, v);
    
    int diff = depth[u] - depth[v];
    
    // Lift u up to same depth as v
    for (int j = 0; j < LOG; j++) {
        if ((diff >> j) & 1) {
            u = up[u][j];
        }
    }
    
    if (u == v) return u;
    
    // Binary search for LCA
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }
    
    return up[u][0];
}

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
```

**Codeforces Problems**:

| Problem            | Rating | Link                                         |
| ------------------ | ------ | -------------------------------------------- |
| Company Queries I  | 1300   | [CSES](https://cses.fi/problemset/task/1687) |
| Company Queries II | 1400   | [CSES](https://cses.fi/problemset/task/1688) |

***

## Pattern 3: Tree DP

### Subtree DP

**Problem**: Compute something for each subtree.

```cpp theme={null}
// Example: Count nodes in each subtree with value > threshold
vector<int> subtreeCount(n + 1);

void dfs(int u, int p) {
    subtreeCount[u] = (val[u] > threshold) ? 1 : 0;
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            subtreeCount[u] += subtreeCount[v];
        }
    }
}
```

### Rerooting DP

**Problem**: Compute answer for each node as if it were the root. A naive approach would run a separate DFS for each root--O(n^2) total. Rerooting DP does it in O(n) with two DFS passes.

**The Trick**: First compute the answer for one root (say node 1) using a standard DFS. Then, in a second DFS, "re-root" the tree to each child by adjusting the parent's answer. When we move the root from u to its child v, the distances to nodes in v's subtree decrease by 1 each, while distances to all other nodes increase by 1 each.

```cpp theme={null}
// Example: Sum of distances from each node to all other nodes
vector<long long> down(n + 1);  // Sum of distances to subtree
vector<long long> up(n + 1);    // Sum of distances to non-subtree
vector<int> sz(n + 1);

void dfs1(int u, int p) {  // Compute down[u] and sz[u]
    sz[u] = 1;
    down[u] = 0;
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs1(v, u);
            sz[u] += sz[v];
            down[u] += down[v] + sz[v];
        }
    }
}

void dfs2(int u, int p) {  // Compute up[u]
    for (int v : adj[u]) {
        if (v != p) {
            // up[v] = up[u] + (contribution from u's other children)
            // + distance to u + (n - sz[v]) nodes above v
            up[v] = up[u] + down[u] - down[v] - sz[v] + (n - sz[v]);
            dfs2(v, u);
        }
    }
}

// Answer for node u = down[u] + up[u]
```

***

## Pattern 4: Centroid Decomposition

**Problem**: Efficiently answer path queries on trees.

The centroid is a node whose removal leaves no subtree larger than n/2. Every tree has at least one centroid, and at most two.

**Analogy**: The centroid is the "center of gravity" of the tree. If you tried to balance the tree on a single node like a mobile, the centroid is where it balances -- no side is too heavy.

**Why it works for path queries**: After finding the centroid and removing it, the tree splits into subtrees of size at most n/2. We solve for all paths through the centroid, then recursively solve each subtree. Since subtrees are at most half the size, there are at most O(log n) levels of recursion, giving O(n log n) total work for many problems.

**When to use**: Path queries that involve counting or aggregation (paths of length k, closest pair in tree, etc.) where direct LCA-based solutions would be too slow.

```cpp theme={null}
vector<int> subtree(n + 1);
vector<bool> removed(n + 1, false);

int getSubtree(int u, int p) {
    subtree[u] = 1;
    for (int v : adj[u]) {
        if (v != p && !removed[v]) {
            subtree[u] += getSubtree(v, u);
        }
    }
    return subtree[u];
}

int getCentroid(int u, int p, int treeSize) {
    for (int v : adj[u]) {
        if (v != p && !removed[v] && subtree[v] > treeSize / 2) {
            return getCentroid(v, u, treeSize);
        }
    }
    return u;
}

void decompose(int u) {
    int treeSize = getSubtree(u, -1);
    int centroid = getCentroid(u, -1, treeSize);
    
    removed[centroid] = true;
    
    // Process centroid - all paths through centroid
    // ...
    
    for (int v : adj[centroid]) {
        if (!removed[v]) {
            decompose(v);
        }
    }
}
```

***

## Pattern 5: Small-to-Large Merging

**Problem**: Aggregate information from children efficiently.

```cpp theme={null}
// Example: Count distinct values in each subtree
vector<set<int>> nodeSet(n + 1);
vector<int> answer(n + 1);

void dfs(int u, int p) {
    nodeSet[u].insert(val[u]);
    
    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
            
            // Merge smaller set into larger
            if (nodeSet[u].size() < nodeSet[v].size()) {
                swap(nodeSet[u], nodeSet[v]);
            }
            
            for (int x : nodeSet[v]) {
                nodeSet[u].insert(x);
            }
            nodeSet[v].clear();
        }
    }
    
    answer[u] = nodeSet[u].size();
}
```

**Complexity**: O(n log² n) total due to small-to-large merging.

***

## Pattern 6: Tree Isomorphism

**Problem**: Check if two trees have the same structure.

```cpp theme={null}
map<vector<int>, int> hashMap;
int nextHash = 0;

int getHash(int u, int p) {
    vector<int> childHashes;
    
    for (int v : adj[u]) {
        if (v != p) {
            childHashes.push_back(getHash(v, u));
        }
    }
    
    sort(childHashes.begin(), childHashes.end());
    
    if (hashMap.find(childHashes) == hashMap.end()) {
        hashMap[childHashes] = nextHash++;
    }
    
    return hashMap[childHashes];
}

bool isIsomorphic(tree1, tree2) {
    // Trees are isomorphic if they have same hash when rooted at centroid
}
```

***

## Common Mistakes

<Warning>
  **Mistake 1: Forgetting parent check in DFS**

  ```cpp theme={null}
  // WRONG - infinite loop
  for (int v : adj[u]) {
      dfs(v, u);  // Will revisit parent!
  }

  // CORRECT
  for (int v : adj[u]) {
      if (v != p) dfs(v, u);
  }
  ```
</Warning>

<Warning>
  **Mistake 2: Wrong Euler tour indices**
  Subtree of u is `[tin[u], tout[u])`, not `[tin[u], tout[u]]`.
</Warning>

<Warning>
  **Mistake 3: LCA on unprocessed tree**
  Always call `preprocess(root)` before LCA queries.
</Warning>

***

## Practice Problems

### Beginner (1000-1300)

| Problem          | Pattern       | Link                                         |
| ---------------- | ------------- | -------------------------------------------- |
| Tree Diameter    | Two BFS       | [CSES](https://cses.fi/problemset/task/1131) |
| Subordinates     | Subtree size  | [CSES](https://cses.fi/problemset/task/1674) |
| Tree Distances I | Tree diameter | [CSES](https://cses.fi/problemset/task/1132) |

### Intermediate (1300-1600)

| Problem           | Pattern                 | Link                                         |
| ----------------- | ----------------------- | -------------------------------------------- |
| Distance Queries  | LCA                     | [CSES](https://cses.fi/problemset/task/1135) |
| Tree Distances II | Rerooting               | [CSES](https://cses.fi/problemset/task/1133) |
| Counting Paths    | Euler tour + difference | [CSES](https://cses.fi/problemset/task/1136) |

### Advanced (1600-1900)

| Problem         | Pattern            | Link                                         |
| --------------- | ------------------ | -------------------------------------------- |
| Distinct Colors | Small-to-large     | [CSES](https://cses.fi/problemset/task/1139) |
| Path Queries II | LCA + segment tree | [CSES](https://cses.fi/problemset/task/2134) |

***

## Key Takeaways

<CardGroup cols={2}>
  <Card title="Euler Tour" icon="rotate">
    Flattens tree to array for range queries on subtrees.
  </Card>

  <Card title="Binary Lifting" icon="stairs">
    O(log n) LCA queries after O(n log n) preprocessing.
  </Card>

  <Card title="Rerooting DP" icon="arrows-spin">
    Compute answer for all roots in O(n) total.
  </Card>

  <Card title="Small-to-Large" icon="scale-balanced">
    Merge smaller sets into larger for O(n log² n).
  </Card>
</CardGroup>

***

## Next Up

<Card title="Chapter 16: Disjoint Set Union" icon="arrow-right" href="/courses/competitive-programming/16-dsu">
  Master Union-Find for dynamic connectivity and Kruskal's MST.
</Card>