Breadth-first search and Binary Search Trees

When we talk about trees, this time, we’re talking about binary trees. Binary trees are data structures that retain relationships to nodes. In programming, we use Breadth-first Search to allow us to search for values via the shortest path to a node’s value. There are many different types of binary trees, but a binary tree is a data structure where each node has up to two children.

This is a binary tree. It has no order because of the leaf (last node) with the value of 12 as a child of the node with the value of 4.

This is a binary search tree. Each node has up to two children and from the left, to root, to the right, all the values ascend in order.

In the second graphic above, you can see that this binary search tree’s root value, 8, has two node children. It’s left child is 4 and it’s right child is 10. Notice that all the values on the left of 8 are less that it? Whereas all the values on the right of 8 are larger than it? This is an important organizational structure of a binary search tree that makes it so unique from other trees.

While binary trees are important to identify, there are other tree forms as well: Complete binary trees, Full binary trees and Perfect binary trees.

This is a Complete tree because it fills from left to right. If the leaf with the value of 15 was on the right side of it’s parent node, that is an incomplete tree. It needs to be filled from left to right.

A Complete binary tree is where every node of the tree is filled except for, sometimes, the last level.

This is a full binary tree

A Full Binary tree is a tree where each node has either 2 children or 0 children.

A perfect tree

A Perfect Binary tree is a tree where every node has two children except for the last level.

It is imperative for a software engineer to understand the key differences in these trees. In an interview it is important to clarify with your interviewer which tree you are working with. Now that we have discussed different types of binary trees, we should discuss transversal methods. Today, we will discuss Breadth-first search. When conducting breadth-first search, ask yourself two questions:

1. What are the starting points? Is there a path to get from A —> B?
2. What is the shortest path to achieve that?

You can think of Breadth-first search like linkedIn. For example, lets say you’re a recent graduate looking for a software engineering job. You would first ask, “who in my network (who is a 1st connection) is a tech recruiter?”. If no one in your network is a tech recruiter, but you know that Sarah, who is a 1st connection to you, may have a tech recruiter connection, you’ll ask, “Who in Sarah’s connections is a tech recruiter (2nd connection)?” and finally, if no one in Sarahs network is a tech recruiter, then you’ll go through Sarah’s connections to find a tech recruiter and so on. Breadth-first Search finds the closest result by checking the nearest node and extending outward.

Checking 1st, 2nd and then 3rd connections starting from your network outward to find who’s a tech recruiter.

Breadth-first search checks your network, then your second connections and then your third connections. Certainly Breadth-first search prefers who’s a tech recruiter in your nearest/closest connection first. However, if it doesn’t find it’s result that it is looking for, it adds more search queries to it’s queue.

What this means is, Breadth-first Search went through ALL of your connections (let’s say you have 150 connections on linkedIn). If none of those 150 connections is a tech recruiter, then it goes through a connections network and so on. It piles more to its queue to search through.

To clarify, a Breadth-first Search takes in three arguments: the tree (the data structure itself), the root node, and the value it is searching for. To relate to our example earlier, the search value is the tech recruiter we’re looking for, the root node is you, your linkedin, which is the starting point. And finally, the tree is the connections you have (in this example, you have 150).

While this is the idea behind Breadth-first search, here is an example of what the code could look like:

let BreadthFirstSearch = (tree, rootNode, searchValue) => {
       let queue = []
       queue.push(rootNode)
       while (queue.length > 0) {
          let currentNode = queue[0]
        if (currentNode.value === searchValue) {
          console.log('the node we were looking for!' +                                       
          currentNode.value)
          return 
        }
        if (currentNode.left ! == null) {
            queue.push(tree[currentNode.left])
        }
        if (currentNode.right ! == null) {
            queue.push(tree[currentNode.right])
        }
       queue.shift()
     }
}

That’s it ! You’re done! You’ve completed your Breadth-first search on a binary tree.

Thanks for reading my blog! Here are some additional resources/blogs I recommend checking out:

https://levelup.gitconnected.com/finding-the-shortest-path-in-javascript-pt-1-breadth-first-search-67ae4653dbec