Binary Trees (Part 5) - Stay Abreast of Breadth-First Search

This week's blog post is a continuation of last week's article about Depth-First Searches and Traversals in binary trees where I briefly compared Depth-First (DFS) and Breadth-First (BFS) Searches and then went into more depth explaining three common DFS methods: in-order, pre-order, and post-order. For today's blog post, I'd like to discuss a couple of situations where we'd use DFS or BFS, and also share some code to explain how BFS works.

A Quick Review of DFS and BFS

As discussed in my previous post, DFS allows us to recursively traverse through a binary tree, diving deeply, edge-by-edge, and exhaustively exploring one branch of a tree before backtracking to the next unvisited branch, whereas BFS or Level-First Traversals allow us to visit nodes of the tree level-by-level.

Here's an (imperfect, but relatable) metaphor to help us visualize how DFS and BFS might process nodes.

Imagine the binary tree as a buffet spread -- a long counter lined with various trays of food. DFS and BFS are eating tonight, and each has a different strategy for dining and traversing this buffet.

BFS, like most of us, would take a serving of each dish onto its plate as it makes a single pass along the buffet counter. After it completes a pass, it would return to the start of the buffet counter and go another round. Each time, the food in all the trays would make it onto BFS's plate and eventually into its mouth.

DFS, on the other hand, would start at the first tray of the buffet counter lineup and keep scooping food until it's reached the bottom of the container. And only when it's completely emptied that tray, it would move onto the next tray in line and proceed to empty that one as well.

Breadth-First Search

In BFS, we traverse a tree from top to bottom, left to right, so when we're processing the node values, we're doing so across levels. After we've exhausted all the nodes in a level, we proceed down to the next level.

Steps to Breadth-First Search:

Before beginning the search, create the following:

• a queue to keep track of all the nodes and their children that we'll need to process and
• a result array to print the nodes in order.

To begin the traversal, first push the root node into the queue. Then,

1. Assign the first node in the queue to be the current node,
2. Process/Print the current node,
3. If the current node has a left child, push the left child node into the queue,
4. If the current node has a right child, push the right child node into the queue, and
5. Shift or remove the first node from the queue.

Repeat steps 1 - 5 until the queue is empty again.

Code: Printing Nodes in BFS Order

bfs(root) {
  let result = [];
  let queue = [];

  queue.push(root);

  while(queue.length) {
    let curr = queue.shift();
    result.push(curr.value)
    if (curr.left) {
      queue.push(curr.left)
    }
    if (curr.right) {
      queue.push(curr.right)
    }
  }

  return result;
}

Code Explanation:

You may recall that in DFS, we'd traverse a tree using recursion. The call stack that results from recursion would help us keep track of which node needed to be processed or bookmarked for later.

However, in BFS, we'd use a queue* to keep track of the nodes that need to be processed. The first in the queue is always the current node, and it's usually followed by a sibling node or a descendant node of the next level below. When we handle the current node, we process its value before we add their left and right children to the queue so that they can be processed later.

What are other differences between DFS and BFS?

As far as run-time goes, DFS and BFS are the same at O(V+E) (V for vertices and E for edges) or simply O(N) because both searches will visit every node in the tree once.

And with regards to extra space, DFS requires O(H) space, where H stands for the maximum height of the tree. It requires O(H) space because of recursion and the function call stack that stores all the node ancestors as we traverse further down the tree. BFS also requires extra space, O(W), where W stands for the maximum width of the tree. This is because the queue at a maximum must keep track of all of the descendants at the widest level of the tree.

What can we do with DFS and BFS?

Now that we know how DFS and BFS work, we need to know what advantages one has over the other and situations when these searches could be applied!

A target or a solution's distance from the root can be a deciding factor in which search to apply. For example, if we suspect that a target node is located deep inside of a tree, possibly closer to a leaf node, we might opt to use DFS because it searches nodes from leaves to root. However, if we're fairly certain that a node is located closer to the root instead, it would be wiser to use BFS since it searches from root to leaves.

In addition, if you're searching for the shortest path from root to node, BFS is an obvious and efficient choice. DFS, however, is less ideal because even though it will always find the target node, it may not take the shortest route, especially because of how it dives deeply in and out of branches.

Finally, DFS is more suitably used for games where decision making is involved in finding a solution. Think of finding the exit in a maze or encountering success in a quest or choose your own adventure game. BFS wouldn't be as useful in these situations though because it doesn't exhaustively explore paths the way that DFS does. However, while we're still on the topic of games, BFS is more concerned with finding the shortest path, so it might be better suited for a puzzle like a Rubik's cube where the goal is to solve the puzzle, not after exhausting all possibilities, but in as few turns as possible.

Check out these pages by GeeksforGeeks if you're interested in learning more about where to apply Depth-First and Breadth-First Traversals!

Conclusion

That's all for Breadth-First Search, and for all things binary trees!

This Binary Tree Blog Series all started with a couple of binary tree problems that I wasn't able to solve and then an obsessive desire to understand it better. This series is by no means a full and comprehensive guide to binary trees, but I hope that it's informative enough to help ease other newbie programmers like myself into learning more about the topic!

Thanks for reading and learning along with me!

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

• Part 1 - The Basics
• Part 2 - Binary Search Trees (Insertion and Search)
• Part 3 - Node Deletion
• Part 4 - Depth-First Traversals

Footnotes:

• What's the difference between stack and queue data structures? A queue is like a waiting line at a cafeteria, where the first person to show up is also the first to be served and to leave. A stack, on the other hand, is much like a stack of dishes or trays at the cafeteria, where the first ones placed into the stack are later always the last ones to be taken out and used.