✍ Note

You must know this algorithm before entering to interview room.

🕑 Time Complexity = O(V+E)

Vertex is the node like (A, B, C). The line between nodes who is connecting 2 nodes are called as Edges. When we traverse to each vertex and add in to array we take O(V) time.

When we iterate all the children nodes of the current nodes. For Node A we have 3 children nodes and there are 3 edges. For B we have 2 children nodes and 2 edges. Therefore, the Time complexity is O(E).

Therefore, total time complexity is O(V+E)

</p>

☁ Space Complexity = O (V)

Since we are calling DFS recursively. And for every recursive call it will create one entry in the Implicit Memory Stack in computer. Imagine if you had one branch only then you could have called all the nodes (Vertices) and you will have V frames on the implicit memory stack. Therefore, the space complexity is O(V) . Where V=vertices.

</p>

See the Pen Graph-Easy-DFS Answer by Rupesh Tiwari (@roopkt) on CodePen.