Table of contents
Introduction
In this post, I wanna dig into BFS and DFS.
I wanna show some code and go through them slowly.
I don't know what it is with recursion, but I'm so passionate about it. It's so beautiful when you visualize all the work.
Anyways, let's start with DFS, and not me ranting about my love for programming lmao
DFS
Dfs stands for Depth First Search. It means we're gonna go as deep as possible into the tree before we backtrack. Backtracking means we're gonna go back up the call stack.
Let's take a look at an example where we want to find a target.
I think this is a good example because you can see the recursive nature of the algorithm.
When we backtrack in this example, we wanna try the right side. We're gonna take a look at an example too to make it clear.
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
function findTarget(root, target) {
// Base cases ⬇️
// If root is null
// It means the parent's root.right or root.left is null
// We return false back up because we didn't find the target
if (root === null) return false;
// If we find the target, we return true
if (root.val === target) return true;
// When we keep recursing down the left side
// Eventually, we either hit the target or we hit null
// We're gonna return false or true back up the call stack
const leftResult = findTarget(root.left, target);
// If leftResult is true
// We know we hit the target
// That's the only base case where we return true
if (leftResult === true) return true;
// Here we wanna try the right side
// It means the result from recursing root.left is false
// So now we're back up at the parent
// if root.right is null, it'll return false (back up to its parent)
// if true, it'll return true (back up to its parent)
return findTarget(root.right, target);
}
Root is a bit a confusing variable name. It's just the node.
But you can envision each node as the root of its own subtree.
Explaining recursion
One thing I wanna clarify with recursion is that this doesn't happen concurrently. It may look like it if you're new to recursion. But what's happening is that we try the left side first. We just keep doing down the left side until we hit the base case. It's also why base cases are so important when you're doing recursion. Otherwise, you'll end up with a stack overflow. Which just means you're calling the function too many times.
When you call a function, it's adding it to the call stack.
Let's visualize it quickly:
findTarget(2, 3) // At root (2)
// Check if 2 === 3? No
└── leftResult = findTarget(3, 3) // Check left child
// Check if 3 === 3? Yes!
└── return true
// Parent got true from left child
└── return true
In this small snippet, root.left where the root has value 2, it's waiting for the result of findTarget(3, 3), which returns true.
This is just to demonstrate recursion and the call stack.
Maybe I could visualize it better.
CALL STACK RETURNS
---------------------------------------------------
findTarget(2, 3) true ↑
└── waiting for findTarget(3, 3) true ↑
└── return true true ↑
Another one:
Stack Frame 1: findTarget(2, 3)
[waiting...]
⬇
Stack Frame 2: findTarget(3, 3)
[found 3! returning true]
⬆
Stack Frame 1: findTarget(2, 3)
[got true from child, returning true]
I just wanna make it VERY clear that when recursion happens, parent is waiting for the result of the child. You can also say it's paused and will resume when the child returns.
Back to the example
Let's take a look at an example to make it clear.
Let's say we're looking for 7.
4
/ \
2 7
/ \ / \
1 3 6 8
Here, we would start by going left. We'd keep going left until we hit the base case.
Which will be when we hit null for findTarget(1.left, 7). Then we'd return false. We'd return the right side: findTarget(1.right, 7).
Both return false as they hit null. So when we called findTarget(2.left, 7), it'd return false. We'd then try the right side: findTarget(2.right, 7).
Which would be findTarget(3, 7). It's not the target, so we don't hit the base case. We try the left and right side again, both return false.
They return false so when we do return findTarget(2.right, 7), it'd return false back to up 4 which will try its right side now.
To be clear, we started with leftResult = findTarget(4.left, 7). It's false. So now we try the right side: findTarget(4.right, 7).
Yes, we hit the base case! So we return true.
When we do return findTarget(4.right, 7), it'd return true as the result of the entire function.
BFS
BFS stands for Breadth First Search. It means we go level by level.
Let's take a look at an example.
4
/ \
2 7
/ \ / \
1 3 6 8
We'd start with 4 obviously. Then we go through 2 and 7. Then we go through 1, 3, 6, and 8.
The key here is using a queue. Each time you wanna go through a level, you take a snapshot of the queue's length and go through that many nodes. A queue is a first in first out data structure. The reason you need to take a snapshot is because the queue will update. When you refer to queue.length, you're referring to the reference's length if that makes sense.
We take the first node from the queue, not the last. Because the queue will update since we'll add the left (if it exists) and right (if it exists) children to the queue.
Let's take a look at the code:
function findTarget(root, target) {
const queue = [root];
while (queue.length > 0) {
let length = queue.length;
for (let i = 0; i < length; i++) {
const node = queue.shift();
if (node.val === target) return true;
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
return false;
}
This is our find target example but this time using bfs.
Another common example is grouping current level nodes and returning an array of arrays.
This is a typical exercise for bfs.
function levelOrder(root) {
const queue = [root];
const result = [];
while (queue.length > 0) {
const length = queue.length;
const currentLevel = [];
for (let i = 0; i < length; i++) {
const node = queue.shift();
currentLevel.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(currentLevel);
}
return result;
}
We'd return something like [[4], [2, 7], [1, 3, 6, 8]].