Level order traversal using queue in java

Java program for Level order traversal using queue. Here problem description and other solutions.

/*
  Java program for
  Level order tree traversal using queue
*/
// Create Q node
class QNode
{
    public TreeNode data;
    public QNode next;
    QNode(TreeNode node)
    {
        this.data = node;
        this.next = null;
    }
}
// Binary Tree Node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class MyQueue
{
    public QNode head;
    public QNode tail;
    public int count;
    public MyQueue()
    {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }
    public int size()
    {
        return this.count;
    }
    public boolean isEmpty()
    {
        return this.count == 0;
    }
    // Add new node of queue
    public void enqueue(TreeNode value)
    {
        // Create a new node
        QNode node = new QNode(value);
        if (this.head == null)
        {
            // Add first element into queue
            this.head = node;
        }
        else
        {
            // Add node at the end using tail 
            this.tail.next = node;
        }
        this.count++;
        this.tail = node;
    }
    // Delete a element into queue
    void dequeue()
    {
        if (this.head == null)
        {
            // Empty Queue
            return;
        }
        // Visit next node 
        this.head = head.next;
        this.count--;
        if (this.head == null)
        {
            // When deleting a last node of linked list
            this.tail = null;
        }
    }
    // Get front node
    public TreeNode peek()
    {
        if (this.head == null)
        {
            return null;
        }
        return this.head.data;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        // Set initial tree root
        this.root = null;
    }
    public void levelOrder()
    {
        if (this.root != null)
        {
            MyQueue q = new MyQueue();
            // Add first node
            q.enqueue(this.root);
            
            TreeNode node = this.root;
            while (q.isEmpty() == false && node != null)
            {
                if (node.left != null)
                {
                    // Add left child node 
                    q.enqueue(node.left);
                }
                if (node.right != null)
                {
                    // Add right child node 
                    q.enqueue(node.right);
                }
                // Display level node
                System.out.print("  " + node.data);
                // Remove current node
                q.dequeue();
                // Get new head
                node = q.peek();
            }
        }
        else
        {
            System.out.println("Empty Tree");
        }
    }
    public static void main(String[] args)
    {
        // Create new tree
        BinaryTree tree = new BinaryTree();
        /*  
          Make A Binary Tree
          -----------------------
                 1
               /   \
              2     3
             /     / \
            4     5   6
           /     / \
          7     8   9
        */
        // Adding tree nodes
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(6);
        tree.root.right.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.left.left = new TreeNode(7);
        tree.root.right.left.left = new TreeNode(8);
        tree.root.right.left.right = new TreeNode(9);
        // Display level order  element 
        tree.levelOrder();
    }
}

Output

  1  2  3  4  5  6  7  8  9



Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2022, kalkicode.com, All rights reserved