Rooted Trees and Tree Representation

Rooting a tree gives every nonroot vertex one parent and turns its remaining neighbors into children. The original edges stay undirected: rooting is an interpretation that lets us describe ancestors, levels, and subtrees. A good representation stores enough information for later queries without duplicating the entire graph.

In competitive programming, adjacency lists are the default way to store sparse trees. Parent and depth arrays are derived from those lists, not competing replacements for them. This lesson builds all three, explains their relationship, and demonstrates how an ordinary BFS creates a useful parent-before-child order.

Prerequisites: Introduction to Trees; vectors, queues, and adjacency lists.

Build the idea

1. 1. Store the undirected structure once

   For edges (1,2), (1,3), (3,4), (3,5), adjacency lists contain graph[1]={2,3}, graph[2]={1}, graph[3]={1,4,5}, graph[4]={3}, and graph[5]={3}. There are 2(N−1) entries because both endpoints store each edge. This takes linear memory, unlike an N by N adjacency matrix. An adjacency list answers “who can I move to?” efficiently, but does not by itself say which neighbor is a parent.

2. 2. Root at an arbitrary vertex

   Choose root 3. Its children become 1, 4, and 5; vertex 1 has child 2. Initialize parent[3]=0 and depth[3]=0. The label 0 is a sentinel meaning “no vertex,” so allocate N+1 positions and keep actual labels in 1..N. When exploring v, the edge to parent[v] leads upward. Every other neighbor is an undiscovered child, because a second route to an already discovered vertex would create a cycle.

   That reasoning uses the promise that the input is a valid connected tree. If arbitrary graphs are allowed, maintain a visited array as well. A parent-only test is not general cycle protection.

3. 3. Build the arrays with BFS

   Put the root into a queue. Remove v, append it to order, and examine its neighbors. For each child next, set parent[next]=v and depth[next]=depth[v]+1 before placing next into the queue. The depth formula works because the unique path from the root to next is the root-to-v path followed by one edge. The first queue layer contains the root; the next contains depth-1 vertices, and so on.

   In the example rooted at 3, parents for vertices 1 through 5 are 3, 1, 0, 3, 3, and depths are 1, 2, 0, 1, 1. These numbers are derived from structure, not the size of labels. A larger label need not be deeper.

4. 4. Recover children, paths, and subtrees

   The children of v are precisely neighbors next with parent[next]=v. Repeatedly following parent[] walks to the root. For example, 2 → 1 → 3 → 0 gives the ancestors of 2. To list a subtree, traverse downward through child edges only; the subtree of 1 is {1,2}. A parent array alone is enough to move upward, but finding all children by scanning all N entries repeatedly can become quadratic. Retain adjacency lists or build explicit child lists when downward traversals matter.

   The BFS order is parent-before-child, useful for depth propagation. Reversing that order makes every child appear before its parent, useful for bottom-up subtree computations. Do not mistake this for an Euler-tour order: BFS positions do not generally make each subtree a contiguous interval.

5. 5. Change the root carefully

   If root changes from 3 to 2, the underlying adjacency lists remain valid, but parent, depth, children, and subtree membership must be rebuilt. Distances between vertices and undirected degrees stay unchanged. This separation is useful in problems that ask whether a property really depends on rooting. Static parent tables, ancestor tables, and entry/exit times become stale after a root change unless a special rerooting method is used.

   The program prints one row per vertex, including its parent and depth, and then the traversal order. It uses a queue rather than recursive calls, so even a long path does not exhaust the call stack.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,root;
    cin>>n>>root;
    // Undirected adjacency lists keep the underlying tree independent of its root.
    vector<vector<int>>graph(n+1);
    for(int i=0;i<n-1;++i){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    // Vertex 0 means "no parent"; the chosen root keeps parent 0 and depth 0.
    vector<int>parent(n+1,0),depth(n+1,0),order;
    queue<int>q;
    q.push(root);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        order.push_back(v); // Every parent appears before its children.
        for(int next:graph[v]){
            if(next==parent[v]){
                continue;
            }
            // Every other neighbor is a child because the input is a valid tree.
            parent[next]=v;
            // The unique root-to-child path is one edge longer.
            depth[next]=depth[v]+1;
            q.push(next);
        }
    }
    for(int v=1;v<=n;++v){
        cout<<v<<' '<<parent[v]<<' '<<depth[v]<<'\n';
    }
    for(int i=0;i<n;++i){
        cout<<order[i]<<(i+1==n?'\n':' ');
    }
}

Complexity analysis

O(N) time to read and root a valid tree; each adjacency entry is examined once. Adjacency lists, arrays, queue, and traversal order use O(N) space. Rebuilding for a new root costs another O(N).

Example input and output

N root, followed by N−1 undirected edges of a valid tree. Output N rows: vertex parent depth; parent of root is 0. The final row is BFS order in adjacency insertion order.

Input

5 3
1 2
1 3
3 4
3 5

Output

1 3 1
2 1 2
3 0 0
4 3 1
5 3 1
3 1 4 5 2

With root 3, vertex 1 lies one edge below 3 and vertex 2 lies below 1. Vertices 4 and 5 are direct children of 3.

Practical applications

Prepare DFS/DP, reconstruct root paths, compute levels, and create ancestor tables. Parent-before-child orders become child-before-parent orders when reversed; this is useful for iterative subtree DP.

Check your understanding

When the root changes, which stored quantity remains unchanged?

Put it into practice

Extend the output with the children of each vertex. Then rerun with root 2 and compare which relationships change.