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;
    }

Solution 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))
{
   ...
}

Solution 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);
}

Comments

[David Weiser]

What have you tried so far? Could you explain, in plain english, what the algorithm should do (i.e give pseudo-code)?

[Kirk Woll]

How 'bout due diligence on Wikipedia? en.wikipedia.org/wiki/Breadth-first_search

[CodesInChaos]

@Via not surprising. A queue is the obvious choice for implementing a breadth-first search, just like you'd use a stack for depth first.

[user3416507]

@CodeInChaos Thanks for your help. Although this is an old post, but I thought I leave a feedback in case it helps somebody. 1) I couldn't get your "fancier solution" to compile. 2) Your original solution worked well. Thanks again.

[Saravanan]

If you could add a comment for down voting, it would be helpful

[ProfK]

A good guess would be that the OP asked for Breadth First and you opening sentence says your answer is for Depth First.

[M.kazem Akhgary]

good comparison for DFS and BFS, I understand DFS but I just couldn't get BFS, so the key to this problem is using a queue instead of stack. thanks.

[Lorenzo]

Also, you're basically allocating more memory than needed by creating a dictionary and many lists which isn't really needed if all you're doing is searching for a specific value

[Lorenzo]

This is probably a stupid suggestion but you could replace both if conditions with a single one that checks for null before matching searchedData; even if it's just 1 line less xD