Depth-First-Search (DFS)— Competitive Programming with Time and Space Complexity

Question

Sample Input:

Input Graph

Sample Output:

Node Class:

public class Node
{
public string name;
public List<Node> children = new List<Node>();
public Node(string name)
{
this.name = name;
}
public Node AddChild(string name)
{
Node child = new Node(name);
children.Add(child);
return this;
}
}

Solution

The problem can be easily solved via recursion. So here we have to move through each depth or the node and return.

private List<string> DepthFirstSearch(Node node, List<string> dfs)
{
dfs.Add(node.name);
foreach (var child in node.children)
{
DepthFirstSearch(child, dfs);
}
return dfs;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store