Tree Traversals (DFS and BFS)

A traversal visits every vertex in a systematic order. Depth-first search follows one branch before returning to other branches; breadth-first search visits vertices by increasing distance from its start. On a tree both reach every vertex in linear time, but the order exposes different information.

DFS supports subtree processing, entry/exit times, and tree dynamic programming. BFS naturally produces distance layers and shortest unweighted paths. The implementation below provides iterative versions of both, so a path with many vertices is safe from recursive stack overflow. Pay attention to the order of neighbors: it changes a traversal order, but never the underlying distances.

Prerequisites: Rooted Trees and Tree Representation; stacks and queues.

Build the idea

1. 1. Follow a small example

   Use edges (1,2), (1,3), (2,4), (2,5), (3,6), rooted at 1. With neighbors in input order, DFS visits 1, 2, 4, 5, 3, 6. It completely explores the branch of 2 before moving to 3. BFS visits 1, 2, 3, 4, 5, 6: all vertices one edge from 1 appear before those two edges away. Neither order means the vertices are sorted by label; that happens here only because of this particular input.

2. 2. Replace recursive DFS with a stack

   A recursive call remembers the current vertex and where execution should resume. For discovery order alone, an explicit stack can store pending vertices. Pop v, record v, and push its children. A stack removes the most recently inserted item, so push neighbors in reverse adjacency order to visit them in forward adjacency order. For vertex 1, pushing 3 then 2 makes 2 run first.

   Set each child’s parent and depth when you push it. Because this is a tree, each nonparent neighbor is reached through only one edge. That guarantees one stack insertion per vertex without a separate visited array. In a general graph, this assumption fails; use visited flags when scheduling vertices. This preorder-only stack does not record exact recursive completion events; later lessons use reversed discovery order or explicit frames when completion matters.

3. 3. Understand what “depth first” guarantees

   Once v is popped, its newly pushed descendants sit above previously pending sibling branches. They are therefore exhausted before those sibling branches. This is why DFS discovery order places the vertices of a rooted subtree together. Parent[] records the unique route back toward the root, and depth increases by one on every child edge. DFS computes correct distances on a tree because there is only one route; on a general unweighted graph DFS does not guarantee shortest distances.

4. 4. Build BFS with a queue

   A queue removes the earliest inserted vertex. After taking a depth-d vertex, append its depth-(d+1) children to the back. Existing depth-d vertices remain ahead of them, so the queue never processes a later layer before an earlier layer. This proves the layer ordering rather than relying on the picture. The BFS implementation assigns distance[next]=distance[v]+1 and uses distance=-1 to represent an undiscovered vertex.

   In the sample, distances for vertices 1 through 6 are 0,1,1,2,2,2. BFS from 4 would have different distances, even though the edges stay unchanged. To reconstruct a path, also store the vertex that first inserted each vertex into the queue.

5. 5. Choose a traversal for the job

   Use BFS to display levels or find a farthest vertex in an unweighted tree. Use DFS discovery order for subtree intervals; use DFS completion or a reversed parent-before-child order for bottom-up calculations. Neither method has an intrinsic lexicographically smallest order: sort adjacency lists if a problem explicitly demands smallest-label choices, at an extra sorting cost.

   The program deliberately prints DFS discovery, BFS discovery, and BFS distances separately. Its DFS parent/depth arrays are local to that traversal, while BFS has its own distance array, so one run cannot accidentally reuse stale visited state from another. For one vertex, both orders contain only the root and its distance is zero.

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

#include<iostream>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
void print(const vector<int>&values){
    for(int i=0;i<(int)values.size();++i){
        cout<<values[i]<<(i+1==(int)values.size()?'\n':' ');
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,root;
    cin>>n>>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);
    }
    vector<int>parent(n+1),depth(n+1),dfsOrder;
    // This stack stores pending discoveries; it does not record recursive exit events.
    stack<int>st;
    st.push(root);
    while(!st.empty()){
        int v=st.top();
        st.pop();
        dfsOrder.push_back(v);
        // Reverse insertion preserves the input order of DFS children.
        for(int i=(int)graph[v].size()-1;i>=0;--i){
            int next=graph[v][i];
            if(next==parent[v]){
                continue;
            }
            // Assign the child relationship before scheduling its discovery.
            parent[next]=v;
            depth[next]=depth[v]+1;
            st.push(next);
        }
    }
    vector<int>distance(n+1,-1),bfsOrder;
    // A FIFO queue visits each distance layer before the next one.
    queue<int>q;
    q.push(root);
    distance[root]=0;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        bfsOrder.push_back(v);
        for(int next:graph[v]){
            if(distance[next]!=-1){
                continue;
            }
            // Mark on insertion so no vertex is enqueued twice.
            distance[next]=distance[v]+1;
            q.push(next);
        }
    }
    print(dfsOrder);
    print(bfsOrder);
    vector<int>result;
    for(int v=1;v<=n;++v){
        result.push_back(distance[v]);
    }
    print(result);
}

Complexity analysis

Each traversal takes O(N) time on a valid tree because there are N vertices and 2(N−1) adjacency entries. The graph, arrays, and explicit stack/queue take O(N) space. Sorting neighbors, if added, costs up to O(N log N).

Example input and output

N root, followed by N−1 edges of a valid unweighted tree. Print DFS discovery order, BFS discovery order, and distances for vertices 1..N. Orders follow adjacency insertion order.

Input

6 1
1 2
1 3
2 4
2 5
3 6

Output

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

DFS finishes the branch under 2 before discovering 3. BFS first visits the root, then 2 and 3, then all depth-2 vertices.

Practical applications

BFS layers support shortest paths, diameter searches, and distance checks. DFS supports flattening, subtree aggregation, and dynamic programming. Both are foundations for all later tree lessons.

Check your understanding

Why does BFS process all depth-d vertices before depth-(d+1) vertices?

Put it into practice

Store a BFS parent for every vertex and print the path from the selected root to a requested target.