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

Question — 9 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve an easy problem, Depth First Search in Binary Tree.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Code Wrestling

Question

You’re given a Node class that has a name and an array of optional children nodes. When put together, nodes form an acyclic tree-like structure.

Implement the depthFirstSearch method on the Node class, which takes in an empty array, traverses the tree using the Depth-first Search approach (specifically navigating the tree from left to right), stores all of the nodes’ names in the input array, and returns it.

Sample Input:

Input Graph

Sample Output:

[“A”, “B”, “E”, “F”, “I”, “J”, “C”, “D”, “G”, “K”, “H”]

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;
        }
}

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

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

So if you have observed the class Node, then each node has a name and children. So the approach is to store the name, and traverse each child in the children until you reach the child’s depth.

Thus, the below code snippet will help you solve the problem:

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

The time complexity is O(v + e) where v is vertex and e is edges. Because we are storing each vertex (each node present in array) thus O(v) and also for each vertex we are doing a for loop and the number depends on the number of edges that vertex has, thus O(e), and hence total is O(v + e).

The space complexity will be O(v) as we are storing vertex in the final result.

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff.

Code Wrestling