Breadth-First Search/Level order Traversal in a Binary Tree

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package levelordertraversalbfs;

/* Write a program for Level order traversal in Binary tree

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.

Here we are using Linked List queue to Store tree node for Level order traversing

*/

import java.util.Scanner;

/**
 *
 * @author shabhatn
 */

class LLNode
{
    LLNode link;
    Node data;
   
    public LLNode()
    {
        link = null;
        data = null;
    }
    public LLNode(Node data , LLNode n)
    {
        this.data = data;
        link = n;
    }

    public LLNode getLink() {
        return link;
    }

    public void setLink(LLNode link) {
        this.link = link;
    }

    public Node getData() {
        return data;
    }

    public void setData(Node data) {
        this.data = data;
    }
   
}

class LL_Queue
{
    LLNode front , rear;
   
    int size;
   
    public LL_Queue()
    {
        front =null;
        rear =null;
        size = 0;
    }
    public int getSize()
    {
        return size;
    }
    public boolean isEmpty()
    {
        return front==null;
    }
   
    public void enqueue(Node data)
    {
        LLNode nptr = new LLNode(data,null);
       
        if(front==null)
        {
            front = nptr;
            rear = nptr;
           
        }
        else
        {
            rear.setLink(nptr);
            rear = nptr;
           
        }
        size++;
       
    }
    public Node dequeue()
    {
        if(isEmpty())
        {
         return null;
        }
        else
        {
            Node d = front.getData();
            front = front.getLink();
            return d;
        }
       
    }
}

class Node
{
    Node Left , Right;
    int data;
   
    public Node()
    {
        Left = null;
        Right = null;
        data = 0;
    }
    public Node(int d)
    {
        Left = null;
        Right = null;
        data = d;
    }

    public Node getLeft() {
        return Left;
    }

    public void setLeft(Node Left) {
        this.Left = Left;
    }

    public Node getRight() {
        return Right;
    }

    public void setRight(Node Right) {
        this.Right = Right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }
   
}

class Binary_tree
{
    Node root;
   
    public Binary_tree()
    {
        root = null;
    }
    public boolean isEmpty()
    {
        return root ==null;
    }
    public void insert(int data)
    {
        root = insert_tree(root,data);
    }
    public Node insert_tree(Node node, int data)
    {
        if(node==null)
        {
            node  = new Node(data);
        }
        else
        {
            if(node.getLeft()==null)
            {
                node.Left = insert_tree(node.Left,data);
            }
            else
            {
                node.Right = insert_tree(node.Right,data);
            }
        }
        return node;
    }
   
    public void Level_order()
    {
        Level_order_traversal(root);
    }
    public void Level_order_traversal(Node root)
    {
        Node temproot;
        LL_Queue lq = new LL_Queue();
        if(root==null)
        {
            System.out.print("No data");
        }
        else
        {
        lq.enqueue(root);
        while(!lq.isEmpty())
        {
            temproot = lq.dequeue();
            System.out.print("-->"+temproot.getData());
            if(temproot.getLeft()!=null)
            {
                lq.enqueue(temproot.getLeft());
            }
            if(temproot.getRight()!=null)
            {
                lq.enqueue(temproot.getRight());
            }
        }
        }
    }
   
}



public class LevelOrderTraversalBFS {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
       
        Binary_tree bt = new Binary_tree();
       
        char ch;
        Scanner sc = new Scanner(System.in);
        do
        {
     
        System.out.println("enter data");
       
        int data = sc.nextInt();
       
        bt.insert(data);
        System.out.println("enter y to add more values to binary tree");
       
        ch = sc.next().charAt(0);
        }while(ch=='y'||ch=='Y');
        System.out.println();
        System.out.print("Level order traversal :->");
        bt.Level_order();
    }
   
}