The depth-first search problem was great practice involving a tree. My initial attempts at the solution were iterating through in essentially a breadth-first search way, but after working through it, I managed to figure out how to use recursion in order to drill all the way down one branch before moving to a sibling node.
Here is a quick definition of depth-first search.
Problem
We're given a Node class with a name and an array of optional children nodes. The nodes form a tree structure.
We're tasked with implementing the depthFirstSearch function on the Node class, and the function takes in an empty array. The function is supposed to traverse the tree with the Depth-first Search approach, store all of the nodes' names in the array and return the array.
Our tree will look like this:
A
/ | \
B C D
/ \ / \
E F G H
/ \ \
I J K
With the depth-first search approach, we want to return an array that looks like this:
["A", "B", "E", "F", "I", "J" "C", "D", "G", "K", "H"]
Approach
We want to add all of the nodes' names in one branch to the final array before moving on to the next branch. So first, we start at root node "A", then go to its first child "B", then go to the child of "B", which is "E". Those names are now all in the array. There are no children of "E", so once we complete that branch, we go back up to "B" and check if it has other child nodes. "B" does have another child "F". We add "F" and check if it has children, and it does. We add its child "I", check if it has children, and it does not. We go back up to "F" and add its child "J" to the array. "J" does not have children so we go back up to "F", which has no more children, go back up to "B" which has no more children, so we're back at "A". We repeat the process with "C", and then "D".
We'll be using a for loop and a recursive approach to solve this problem.
The way I approached it was by keeping track of a currentNode throughout the function. First step is to add the currentNode's name to the array. Then we loop through the children of the currentNode, and we recursively call the depthFirstSearch function again on any child nodes of the currentNode. This is how we drill down the same branch and add all the children on one branch to the array before moving to the next sibling of the currentNode.
Lastly, we return the array with all of the node names.
Solution
We're working on the function depthFirstSearch within the given Node class. This gives us access to the this keyword, to reference the currentNode instance we are working with.
class Node {
constructor(name) {
this.name = name;
this.children = [];
}
depthFirstSearch(array) {
}
}
We have access to this, so I saved it to a variable currentNode for easy tracking.
depthFirstSearch(array) {
let currentNode = this;
}
We push the currentNode's name into the array.
depthFirstSearch(array) {
let currentNode = this;
array.push(currentNode.name);
}
Next, we begin our for loop to iterate through our currentNode's children.
depthFirstSearch(array) {
let currentNode = this;
array.push(currentNode.name);
for (let child of currentNode.children) {
}
}
This part is key, because our recursion occurs in the for loop.
As we loop through each child, we reassign currentNode to be the currentNode's child. Next step is we call the depthFirstSearch function on that child. This means we go through the function again, but with this child node instead. We add that child node's name to the array, then we enter the for loop and iterate through that child node's children, and repeat the process.
depthFirstSearch(array) {
let currentNode = this;
array.push(currentNode.name);
for (let child of currentNode.children) {
currentNode = child;
currentNode.depthFirstSearch(array);
}
}
Lastly, we return the array for our answer.
depthFirstSearch(array) {
let currentNode = this;
array.push(currentNode.name);
for (let child of currentNode.children) {
currentNode = child;
currentNode.depthFirstSearch(array);
}
return array;
}
Inside the Node class, it looks like this:
class Node {
constructor(name) {
this.name = name;
this.children = [];
}
depthFirstSearch(array) {
let currentNode = this;
array.push(currentNode.name);
for (let child of currentNode.children) {
currentNode = child;
currentNode.depthFirstSearch(array);
}
return array;
}
}
Resources
Top comments (0)