BFS (Breath First Search) Introduction
This search basically goes from left to right at every level of the tree. So if you had the following tree:
A breadth first search would run through this tree in this order starting from the top level:
9 → 6 → 12 → 1 → 4 → 34 → 45
See how it goes left to right at each level going from the top level and then down a level and then going left and right again until it reaches the bottom level? It is essentially searching every node by searching every node at each level.
BFS uses additional memory because it is necessary to track all the nodes on a given level while searching that level, this means that we need to track every node and its children in order.
DFS (Depth First Search) Introduction
Depth first search (DFS) follows one branch of the tree down as many levels as possible until the target node is found or the end of the branch is reached.
When the search can’t go on any further, it goes back up to the nearest ancestor (parent node) with an unexplored child (child node that has not be gone down) and then continues down that child’s branch until it can’t anymore.
So let’s go back to this example:
For DFS we prioritize going down as deep as possible, so we start at the root node, 9. Then we go to 6 and then 1. But then we see that there are no more children after 1 (it is a leaf node). So then we go back up to 6 since it is the nearest ancestor that still has unexplored child nodes and from there we go to its unexplored child which is the node with the value of 4.
We then see that there is no more children after 4 so we go back up to 6, see that 6 no longer has any child nodes that are unexplored, so we go back up to 9 and see that we have unexplored child nodes, so we go to the unexplored child node which is 12. Then we go to 34. We see that 34 has no children (is a leaf node), so we go back up to 12, see that it has an unexplored child node of 45 and then we go to 45.
Does that make sense? We go as far down as we can first before checking every other vertical “branch”.
9 → 6 → 1 → 4 → 12 → 34 → 45
DFS has a lower memory requirement than BFS because it’s not necessary to store all the child pointers at each level.
BFS vs DFS
BFS is like checking everything on one floor of a building before going to the next floor.
DFS is like going all the way down and then checking if there are any stairs you forgot to go down and checking down those.
In interviews, you’ll be asked about what type of traversal to do and usually you’ll have to answer BFS or DFS.
All traversals are O(n) so for both BFS and DFS, the time complexity is O(n).
The order is the thing that matters when it comes to BFS and DFS.
Extra Resources for BFS vs. DFS
https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr
Exercise: BFS vs DFS
If you know a solution is not far from the root of the tree: BFS (breadth first search)
If the tree is very deep and solutions are rare: BFS (breadth first search) this is because the tree is already very deep meaning that DFS would took a long time just to search even one branch and because the solution is rare it will take a long time per branch (BDS however has memory concerns)
If the tree is very wide: DFS (depth first search) — this is because if the tree is wide and a BFS is very memory-intensive then storing all the children for each node will take up a lot of memory
If solutions are frequent but located deep in the tree: DFS (depth first search)
Determining whether a path exists between two nodes: DFS (depth first search)
Finding the shortest path: BFS (breadth first search)
breadthFirstSearch()
We have to keep track of every child node, so that we can go back and visit each of the children nodes. This is why BFS is so memory-intensive.
Let’s implement a breadth first search (BFS) on the example tree from above:
breadthFirstSearch(){
//the currentNode starts at the head or the root node to begin its search
let currentNode = this.root;
//the list is an array where we store the values of the nodes that we will return
let list = [ ];
//the queue array below will store all of the child nodes (stores the nodes, not the
value of the nodes which are stored in list, we need to store the nodes so that we can
reference the left and right properties of the nodes to get the child nodes) of the level we are on, so this is where we run into possible memory and storage issues because we might have to store too many child nodes
let queue = [ ];
//we first push the root node into the queue array because that will be the first node
we check and the first node we will be extracting child nodes from
queue.push(currentNode);
//the while loop keeps running until the queue array is empty which means that there
are no more children to explore
while(queue.length > 0){
//we set the currentNode to the first item in the queue array
the shift() function removes and returns the first item in the array
currentNode = queue.shift();
//we then add the value of the currentNode to the list
list.push(currentNode.value);
//if the a child node exists to the left of the currentNode, we push that node to
the queue array where we store nodes that we have to check for children
if(currentNode.left){
queue.push(currentNode.left);
}
//if the a child node exists to the right of the currentNode, we push that node
to the queue array where we store nodes that we have to check for children
if(currentNode.right){
queue.push(currentNode.right);
}
}
return list;
};
So to trace the code, we start with 9 as the currentNode. We push the currentNode into the queue array so the queue array current reads: [ {value: 9, this.left: 6, this.right: 12} ]
Then we enter the while loop because the queue array is not empty. First we reach the set the currentNode equal to the first item in the queue array using shift(), which, as of now, only contains the root node of {value: 9, this.left: 6, this.right: 12}
We then add the value of the currentNode into our list that we will return at the end.
So because we used shift() we actually remove the first item from the array so as of now our queue array is temporarily empty with [ ] while we are in the while loop. By the time we reach the end of our first pass through the while loop, we will repopulate it as we see in the code below with the if statements.
With the if statements, we first check if there is a left node, and we check if there is a left node on the currentNode, which is currently {value: 9, this.left: 6, this.right: 12}. There is a left node on currentNode so we push that node into the queue array, repopulating it. The queue array now contains [{value: 6, this.left: 1, this.right: 4}].
Then with the next if statement, we check if there is a right node on the currentNode which is still set to the root node (NOTE: we only change the currentNode on the start of another pass through the while loop, so currently the root node is still the currentNode), {value: 9, this.left: 6, this.right: 12}. There is a right node on currentNode so we push that node into the queue array, adding to the array. The queue array now contains [{value: 6, this.left: 1, this.right: 4}, {value: 12, this.left: 34, this.right: 45}]
The list array currently contains: [9]
Upon another pass through the while loop, since the queue array is not empty, we then set the currentNode to the first item in the queue array with the shift method (remember this removes and returns the first item of the array we call shift on). We then add the value of the current node to the list array.
So currently, the currentNode is {value: 6, this.left: 1, this.right: 4}
The list array is [9, 6]
And the queue array is [{value: 12, this.left: 34, this.right: 45}] since we removed the first item of the array and set it to currentNode
We then check the left and right child nodes of the currentNode, {value: 6, this.left: 1, this.right: 4}, and then push them into the queue array, making it now:
[{value: 12, this.left: 34, this.right: 45}, {value: 1, this.left: null, this.right: null}, {value: 4, this.left: null, this.right: null}]
In the next pass through the while loop we will end up with the following by the end of the pass:
The currentNode will be {value: 12, this.left: 34, this.right: 45}
The list array will be [9, 6, 12]
The queue array will be [{value: 1, this.left: null, this.right: null}, {value: 4, this.left: null, this.right: null}, {value: 34, this.left: null, this.right: null}, {value: 45, this.left: null, this.right: null}]
Do you see how the queue array can be a huge drain on memory now? It can grow way too big if you have too many levels.
DFS: InOrder, PreOrder, PostOrder
There are three ways to implement depth first search (DFS):
InOrder
PreOrder
PostOrder
Let’s use this tree as an example (it is different than the heap we used in BFS):
InOrder is where we use DFS to traverse a binary search tree and return it in order which means that the return has sorted every node value from least to greatest already within the InOrder’s return.
PostOrder on example: [ 1, 4, 6, 9, 15, 20, 170 ]
PreOrder is where we start at the root node and then keep going down one of its children till you can’t go any further down, goes back up to a node that still has children and then goes down that branch until it can’t anymore. PreOrder’s return is good because it makes it easier to recreate a tree because it is ordered that way for us.
PostOrder on example: [ 9, 4, 1, 6, 20, 15, 170 ]
PostOrder is where we go all the way down to the lowest level recording what’s there, and then recording the parent of those two children at the bottom level, traversing back up to reach another two leaf nodes at the bottom level, recording those two, then recording their parent, and so on and so forth. In this case, the children nodes are recorded before their parent nodes. This means that the root node would be the last thing in the array. It goes like [leaf node, leaf node, parent of leaf, leaf node, leaf node, other parent of leaf, parent of parent leaf node, other parent of other parent of leaf node, root node]
PostOrder on example: [ 1, 6, 4, 15, 170, 20, 9 ]
depthFirstSearch()
Now let’s implement a depth first search (DFS). We will write one for InOrder, PreOrder, and PostOrder. So we would have the following (in our tree class that’s why there isn’t a function keyword):
//we return a function in these and they are all recursive simply because of the nature of DFS. we once again must start at the root node and our empty array, or the list, will contain the values of our nodes
DFSInOrder(){
return traverseInOrder( this.root, [ ]);
}
DFSPostOrder(){
return traversePostOrder( this.root, [ ]);
}
DFSPreOrder(){
return traversePreOrder( this.root, [ ]);
}
//now down here we’ll write the functions we are returning in the above DFS’s
//we want the list to have our node values in sorted order for InOrder DFS
function traverseInOrder( node, list ){
//this recursive case says, go all the way to the left until there are no more children
//then add that leftmost value into the list
if(node.left){
traverseInOrder( node.left, list );
}
list.push(node.value);
//we do the same to any right child, we only move onto checking for right children
after checking for left so this ensures that we are not going from the root node directly
to the rightmost node in the tree (see the logic written down below)
if(node.right){
traverseInOrder( node.right, list );
}
list.push(node.value);
return list;
}
Because we are pushing our node values to the list only after we’ve verified the left nodes and traversed all the way down, the lowest numbers get put into the list first.
Let’s word it out by using the above binary tree as an example. So we first traverse down to the leftmost node recursively. This is the node with the value of 1. Since there are no more left nodes, 1 gets pushed into the list array. Then the code checks for right nodes on 1. These do not exist since 1 is a leaf node. It returns the list array as [1] and now we will begin bubbling up the recursion.
With the return of the recursion on the leftmost node of 1, we move up to the previous recursion which was called on its parent node of 4. Since in this part of the recursion we have already fulfilled the conditional in if(node.left), we then move onto the next line of code which is list.push(node.value) which means we then push 4 into the list array: [1, 4]
After that, we move onto the next line of code which is the conditional of if(node.right), and this condition is fulfilled since 4 has a right node of value 6. So because this conditional is fulfilled, we run the code within the if statement which is another recursive function and it runs traverseInOrder() on the right child of 4 which is the node with the value of 6.
Once 6 goes through its recursion, it will have no left nodes and no right nodes so it immediately gets its value pushed into the list array and then returned.
This results in the following list array: [1, 4, 6]
Then we go even further up our recursion and end up on the parent node of 4 which is the root node of 9. Since at this point in unraveling our recursion, we have already fulfilled the code in the conditional if(node.left), we move on to the next line of code, which pushes node.value into the list array so we add the value of 9 to it, resulting in: [1, 4, 6, 9]
Then we move on to the next line of code, which checks for a right child on the 9, and it exists so we will have to execute the code within that if statement which is another recursion, that will be called on the right node of 9, so this is what will be executed: traverseInOrder( node with the value of 20, [1, 4, 6, 9] )
Since we have to go down the entire line of traverseInOrder() again with the node with the value of 20, we will begin with checking to see if 20 has a left child and then keep on going to the left of that, so we will eventually end up at the node with the value of 15 and then push it into the list array, resulting in: [1, 4, 6, 9, 15]
And so on and so forth. You can see now how this will resolve to [ 1, 4, 6, 9, 15, 20, 170 ]
Now that we’ve implemented traverseInOrder() implementing the rest, traversePostOrder() and traversePreOrder() becomes that much easier since it is the same thing but doing things in different order, see below:
function traversePreOrder( node, list ){
//now we want to push at the very beginning because we start with the parent and
then the children and that’s the order of preorder
list.push(node.value);
//checks for a left node
//in the conditional, that recursive function will result in the node being passed in being
pushed into the list array immediately, same for the other conditional for the right
side
if(node.left){
traversePreOrder( node.left, list );
}
if(node.right){
traversePreOrder( node.right, list );
}
return list;
}
//for traversePostOrder we would put list.push(node.value) at the very end of the function
//this is because the order suggested is that we post at the end (postOrder), you can naturally see we must only push the leaf nodes then their parents and then slowly read in values one level at a time going from bottom to top
function traversePostOrder(node, list ){
//traverses all the way to the leftmost leaf node, puts that value into the list array,
loops back out to the previous recursion and then moves down checking of there is a
right child on the parent node of the leftmost leaf node (so this would record 1, the
leftmost leaf node, and then go back up to the parent node and check the second
conditional and see that there is a right node of 6 and push that into the list
if(node.left){
traversePostOrder( node.left, list );
}
if(node.right){
traversePostOrder( node.right, list );
}
list.push(node.value);
return list;
}
If you’ve noticed, we are using a stack data structure with the recursion.
Each of these functions are added to our call stack and will start to return as they reach the end, which is when there’s no more left or right children, which means they’re at the leaf nodes.
And this is important to understand, because it shows the space complexity of DFS (depth first search). The amount of space that we need in terms of memory, unlike BFS (breadth first search) which uses queues, is made apparent by the height of the tree because the height of the tree will match the deepest recursive function. And that’s what will be added to the stack as memory.
This means our memory consumption or space complexity will be O(height of the tree) when using DFS.
Conclusion
Understand when to use BFS vs DFS and how to then implement this for graph traversal.
Top comments (0)