Tree Representations for Competitive Programming
Recursive DFS Optimization
One Pass to Rule Them All
In competitive programming, efficiency is everything. A common task is to understand the structure of a tree, and running multiple traversals to find different properties is too slow. The good news is that we can compute almost everything we need to know about a tree's structure in a single Depth-First Search (DFS) pass.
By augmenting a standard recursive DFS, we can calculate each node's depth, parent, subtree size, and entry/exit times. These properties are the foundation for solving more advanced problems, like finding the Lowest Common Ancestor (LCA) or using dynamic programming on trees.
Let's set up the global arrays we'll use to store this information. Assuming we have N nodes, we'll need:
| Array | Purpose |
|---|---|
parent[N] | Stores the parent of each node. |
depth[N] | Stores the distance from the root. |
subtree_size[N] | Stores the number of nodes in a node's subtree. |
tin[N] | Records the "entry time" of a node in the DFS. |
tout[N] | Records the "exit time" of a node in the DFS. |
Our DFS function will be responsible for filling these arrays. The function signature will look something like dfs(u, p, d), where u is the current node, p is its parent, and d is its current depth. We pass the parent p to avoid immediately traveling back up the tree.
const int MAXN = 200005;
vector<int> adj[MAXN];
int parent[MAXN], depth[MAXN], subtree_size[MAXN];
int tin[MAXN], tout[MAXN];
int timer = 0;
void dfs(int u, int p, int d) {
// 1. Record basic properties upon entering the node
parent[u] = p;
depth[u] = d;
subtree_size[u] = 1; // A node is always in its own subtree
tin[u] = ++timer; // Assign entry time
// 2. Recurse on children
for (int v : adj[u]) {
if (v != p) { // Don't go back to the parent
dfs(v, u, d + 1);
// 3. Update subtree size after child's traversal is complete
subtree_size[u] += subtree_size[v];
}
}
// 4. Record exit time after visiting all children
tout[u] = ++timer;
}
// Initial call from main (assuming root is node 1)
dfs(1, 0, 0); // parent of root is 0, depth is 0
Flattening the Tree with an Euler Tour
The tin and tout arrays might seem abstract, but they perform a powerful transformation. Together, they create what's known as an of the tree. This technique effectively flattens the tree's hierarchical structure into a linear sequence, which is much easier to work with.
The key insight is that for any node u, all the nodes in its subtree are visited by the DFS between the time we enter u (tin[u]) and the time we exit u (tout[u]). This means a node v is in the subtree of u if and only if tin[u] <= tin[v] and tout[v] <= tout[u]. This simple check allows you to answer subtree queries in constant time, a massive advantage for many problems.
Dodging Stack Overflow
Recursive DFS is elegant but has a hidden danger: the call stack. Each recursive call adds a new frame to the to store local variables and the return address. For a deeply nested or long, chain-like tree, this can exceed the default stack size limit, causing a stack overflow crash.
In competitive programming, where constraints can be large ( up to ), a path of length is possible. Most platforms have a stack limit much smaller than this (e.g., 256 MB), so a deep recursion will certainly fail.
So what can we do? The most direct solution is to rewrite the DFS iteratively. Any recursive algorithm can be converted into an iterative one using an explicit stack data structure.
The core idea of an iterative DFS is to manage the traversal yourself using a
std::stack, mimicking what the program's call stack does automatically in the recursive version.
Here’s how an iterative DFS for calculating entry/exit times would look. We push a node onto the stack to signal we are visiting it for the first time (recording tin). We also need a way to know when we are done with a node's entire subtree. A common trick is to push the node a second time, perhaps as its negative, to signify that we are backtracking past it (recording tout).
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
// (Assume same global setup as before)
void iterative_dfs(int start_node) {
std::stack<int> s;
s.push(start_node);
std::vector<bool> visited(MAXN, false);
while (!s.empty()) {
int u = s.top();
s.pop();
// If we are backtracking past u
if (u < 0) {
tout[-u] = ++timer;
continue;
}
// First time visiting u
if (visited[u]) continue;
visited[u] = true;
tin[u] = ++timer;
s.push(-u); // Schedule the exit time calculation
// Add children to the stack in reverse order
// to process them in the correct order.
for (int i = adj[u].size() - 1; i >= 0; --i) {
int v = adj[u][i];
if (!visited[v]) {
s.push(v);
}
}
}
}
// Note: This iterative version only computes tin/tout.
// Calculating parent, depth, and subtree size iteratively
// requires a more complex state management on the stack.
While the iterative approach avoids stack overflow, it is often more complex to write and debug, especially when you need to calculate multiple properties like subtree size. For many problems, the recursive version is fine, but it's crucial to know the iterative alternative exists for when you encounter deep trees.
In a single-pass DFS on a tree, what is the primary reason for passing the parent node p to the function dfs(u, p, d)?
Using the precomputed entry (tin) and exit (tout) times from an Euler Tour, how can you determine if a node v is in the subtree of another node u?