Sunday, November 8, 2015

Level Order Traversal or BFS in a Binary Tree

In a Binary Tree, Level Order Traversal is also known as Breadth-first search or BFS. This BFS is different from a non-Binary Tree Graph.

This program uses the Binary Search Tree program available here: link
The same program can also be used for Binary Tree

//BinarySearchTree Reffers to the link given above
     public String LevelOrder()    {
        Queue<BinarySearchTree> Q = new LinkedList<BinarySearchTree>();
        StringBuffer sb = new StringBuffer();
        Q.add(this); //Inserting Root Node to Queue
        while(Q.size()!=0)    {
            BinarySearchTree CurrentNode = Q.remove();
            sb.append(CurrentNode.data).append(", ");
            if(CurrentNode.left!=null)
                Q.add(CurrentNode.left);
            if(CurrentNode.right!=null)
                Q.add(CurrentNode.right);
        }
        return sb.toString();
    }
UA-39217154-2