# Depth-First Search

Dive into the depth-first search algorithm to traverse graphs and trees with depth as your guide.

DFS
easy

Published At

6/4/2021

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.

If you're unfamiliar with Depth-first Search, we recommend watching the Conceptual Overview section of this question's video explanation before starting to code.

### Sample Input

js
``````graph = A
/  |  \
B   C   D
/ \     / \
E   F   G   H
/ \   \
I   J   K``````
js
``````graph = A
/  |  \
B   C   D
/ \     / \
E   F   G   H
/ \   \
I   J   K``````

### Sample Output

js
``["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]``
js
``["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]``

### Hints

Hint 1

The Depth-first Search algorithm works by traversing a graph branch by branch. In other words, before traversing any Node's sibling Nodes, its children nodes must be traversed. How can you simply and effectively keep track of Nodes' sibling Nodes as you traverse them, all the while retaining the order in which you must traverse them?

Hint 2

Start at the root Node and try simply calling the depthFirstSearch method on all of its children Nodes. Then, call the depthFirstSearch method on all children Nodes of each child node. Keep applying this logic until the entire graph has been traversed. Don't forget to add the current Node's name to the input array at every call of depthFirstSearch.

Optimal Space & Time Complexity

O(v + e) time | O(v) space - where v is the number of vertices of the input graph and e is the number of edges of the input graph

Solution-1
js
``````// Do not edit the class below except
// for the depthFirstSearch method.
// Feel free to add new properties
// and methods to the class.
class Node {
constructor(name) {
this.name = name;
this.children = [];
}

this.children.push(new Node(name));
return this;
}

depthFirstSearch(array) {
array.push(this.name)
for (let i of this.children) {
i.depthFirstSearch(array)
}
return array
}
}

// Do not edit the line below.
exports.Node = Node;``````
Solution-1
js
``````// Do not edit the class below except
// for the depthFirstSearch method.
// Feel free to add new properties
// and methods to the class.
class Node {
constructor(name) {
this.name = name;
this.children = [];
}

this.children.push(new Node(name));
return this;
}

depthFirstSearch(array) {
array.push(this.name)
for (let i of this.children) {
i.depthFirstSearch(array)
}
return array
}
}

// Do not edit the line below.
exports.Node = Node;``````

š®

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek š

## Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

• In-depth looks at my covert projects and musings to ignite your imagination.
• Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
• A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.