DFS of an Acyclic Graph Editorial

Practice Problem Link: DFS of an Acyclic Graph

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given an acyclic graph (n-ary tree) compute its pre-order traversal.

The graph has n nodes indexed 0 to n-1. It is given in the form of an adjacency list and you can consider the node indexed 0 to be the root.

Return the pre-order traversal starting at the root.

Approach

• Start from the root node and add it to the answer array.
• Now traverse its adjacent nodes and for every node except the parent of the current root node, do the above steps recursively.

Analysis

• Time Complexity: O(V + E)
• Auxiliary Space Complexity: O(V)

Where V is the number of nodes and E is the number of edges.

Implementation

C++

void dfsUtil(int root, int parent, vector<vector<int>> &adjList, vector<int> &traversal) {
	traversal.push_back(root);
	for(int i = 0; i < adjList[root].size(); i++) {
		int node = adjList[root][i];
		if (node != parent) {
			dfsUtil(node, root, adjList, traversal);
		}
	}
}
vector<int> dfs(vector<vector<int>> adjList) {
	vector<int> traversal;
    dfsUtil(0, - 1, adjList, traversal);
	return traversal;
}

Java

class Solution {
	void dfsUtil(int root, int parent, ArrayList<Integer>[] adjList, ArrayList<Integer> traversal) {
		traversal.add(root);
		for(int i = 0; i < adjList[root].size(); i++) {
			int node = adjList[root].get(i);
			if (node != parent) {
				dfsUtil(node, root, adjList, traversal);
			}
		}
	}
    ArrayList<Integer> dfs(ArrayList<Integer>[] adjList) {
        ArrayList<Integer> traversal = new ArrayList<Integer>();
		dfsUtil(0, - 1, adjList, traversal);
		return traversal;
    }
}