Please enable JavaScript to view this page content properly.

Tree: Breadth First Search

Please enable JavaScript to view this page content properly.

Problem: Write code for doing a breadth first search in a Tree data structure.

Solution: Breadth first
search inspects items one level at a time starting with the root node.
This is unlike the Depth First Search where the nodes in the left most
branch are visited until there are no more nodes and then backtracks.

The problem with implementing a breadth first search is that we have to
remember the list of nodes at the same level before moving to the next
level. This can be achieved by using a queue data structure. See this
post on details of how to implement a Queue using an array.
Every time we visit a node, we inspect the data contained in the node
before Enqueueing both children to the Queue. If the node contains the
data we were searching for we return the pointer to that node.

//Breadth First Search (BFS) method searches the tree one level at a time