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.
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.
A Complete binary tree is where every node of the tree is filled except for, sometimes, the last level.
A Full Binary tree is a tree where each node has either 2 children or 0 children.
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:
- What are the starting points? Is there a path to get from A —> B?
- 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.
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: