Breadth-first traversal

Question

I was trying to solve one interview question, but for that I have to travel the binary tree level by level. I have designed BinaryNode with having below variable

private object data; private BinaryNode left; private BinaryNode right; 

Could someone please help to write the BreadthFirstSearch method inside my BinarySearchTree class?

Update: Thanks everyone for your inputs. So this was the interview question. "Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)".

Here is my Method, let me know your expert comment.

public List<LinkedList<BNode>> FindLevelLinkList(BNode root)     {         Queue<BNode> q = new Queue<BNode>();         // List of all nodes starting from root.         List<BNode> list = new List<BNode>();         q.Enqueue(root);         while (q.Count > 0)         {             BNode current = q.Dequeue();             if (current == null)                 continue;             q.Enqueue(current.Left);             q.Enqueue(current.Right);             list.Add(current);         }          // Add tree nodes of same depth into individual LinkedList. Then add all LinkedList into a List         LinkedList<BNode> LL = new LinkedList<BNode>();         List<LinkedList<BNode>> result = new List<LinkedList<BNode>>();         LL.AddLast(root);         int currentDepth = 0;         foreach (BNode node in list)         {            if (node != root)             {                 if (node.Depth == currentDepth)                 {                     LL.AddLast(node);                 }                 else                 {                     result.Add(LL);                     LL = new LinkedList<BNode>();                     LL.AddLast(node);                     currentDepth++;                 }             }         }          // Add the last linkedlist         result.Add(LL);         return result;     } 

Answer 1

A breadth first search is usually implemented with a queue, a depth first search using a stack.

Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while(q.Count > 0) {     Node current = q.Dequeue();     if(current == null)         continue;     q.Enqueue(current.Left);     q.Enqueue(current.Right);      DoSomething(current); } 

As an alternative to checking for null after dequeuing you can check before adding to the Queue. I didn't compile the code, so it might contain some small mistakes.

---

A fancier (but slower) version that integrates well with LINQ:

public static IEnumerable<T> BreadthFirstTopDownTraversal<T>(T root, Func<T, IEnumerable<T>> children) {     var q = new Queue<T>();     q.Enqueue(root);     while (q.Count > 0)     {         T current = q.Dequeue();         yield return current;         foreach (var child in children(current))             q.Enqueue(child);     } } 

Which can be used together with a Children property on Node:

IEnumerable<Node> Children { get { return new []{ Left, Right }.Where(x => x != null); } } 

...

foreach(var node in BreadthFirstTopDownTraversal(root, node => node.Children)) {    ... } 

Answer 2

var queue = new Queue<BinaryNode>(); queue.Enqueue(rootNode);  while(queue.Any()) {   var currentNode = queue.Dequeue();   if(currentNode.data == searchedData)   {     break;   }    if(currentNode.Left != null)     queue.Enqueue(currentNode.Left);    if(currentNode.Right != null)     queue.Enqueue(currentNode.Right); }