Technical Interview

Home
Added Recently
Data Structures
Puzzles
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Algorithms
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Links
Contact Us
Submit Question/Answer



Tree: Breadth First Search




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

Node * Breadth-First-Search(Node *root, int searchValue)
{
Queue queue;
queue.Enqueue(root);
Node * currentNode;
while(currentNode = queue.Dequeue())
{
if(currentNode->data == searchVal)
return currentNode;

queue.Enqueue(currentNode->left);
queue.Enqueue(currentNode->right);
}
}