Graph Iterative vs Recursive

Hi Mosh, why the output is different in Recursive and Iterative method in Graph lectures

for the graph the solution for

DFS in Recursive is ABDC
DFS in Iterative is ACBD

please suggest which one is correct or why the output is different there.

IIRC, both were valid because DFS means you can visit nodes at the same depth in any order. If Mosh’s code visited something at a deeper depth before an earlier depth, it would be a bug in his code. If the order is just different, but within the same depth, both answers are valid.

For example, in a fully connected clique with four nodes A to D, all of the following traversals are valid starting at A:


This is because B, C, and D are all at depth 1. If we add a 5th node E which is one hop away from A, but is connected to at least one other node, then the valid traversals would be the same, just adding an E at the end. Everything within the depth 1 set can be in any order, they just have to be visited before anything at depth 2.

In contrast, binary trees have exact ordering depending on if you use preorder, postorder or inorder traversals. Graphs have much greater variety.