-->

Level Order Traversal of binary search tree

Posted by Admin on
Que : Write a program to print the node of tree level wise(one level at a time) . For example if we have the following tree then the output should be  4,2,5,1,3 . 
Aglorithm :

 We will take the help of Queue to print the node of tree level wise . First we will insert the root node in the queue and then insert its left child if exist and then right child node if exist and print them in FIFO order following the same procedure until all the nodes are printed. 
 
1. Initialize a queue.
2. Insert the root into the queue.
3. Repeat steps 4 to 7 until the queue is empty.
4. Delete the node from the queue.
5. Process the node being deleted.
6. If the left child of node exists (is not null), insert it into the queue.
7. If the right child of node exists (is not null), insert it into the queue


Implementation :

class BSTNode {
       int data;
       BSTNode right;
       BSTNode left;

       BSTNode(int d) {
              data = d;
       }
}

// class to create the binary search tree
public class LevelOrderTraversal {
      
       public BSTNode insert(BSTNode p, int key) {
              if (p == null) // if root is null then create a new node
              {
                     p = new BSTNode(key);
              }
              // if num is less than the data of current node then go to left
              else if (key < p.data)
                     p.left = insert(p.left, key);
              // if num is greater than the data of current node then go to right
              else if (key > p.data)
                     p.right = insert(p.right, key);

              // returning root node to maintain it in the BinarySearchTree class
              return p;
       }

       public void levelOrderTraversal(BSTNode p) {
             
              //return if tree is empty or leaf node
              if (p == null) {
                     System.out.println("tree is empty");
                     return;
              }
              java.util.LinkedList<BSTNode> que = new java.util.LinkedList<BSTNode>();
             
              //inserting root node
              que.push(p);
              while (!que.isEmpty()) {
              // printing node and then inserting its child nodes if exist
                     p = que.removeFirst();
                     System.out.print(p.data + " ");
                     if (p.left != null) {
                           que.add(p.left);
                     }
                     if (p.right != null) {
                           que.add(p.right);
                     }
              }
       }

       public static void main(String args[]) {
              LevelOrderTraversal BST = new LevelOrderTraversal();
              BSTNode root = null;
              root = BST.insert(root, 4);
              root = BST.insert(root, 2);
              root = BST.insert(root, 1);
              root = BST.insert(root, 3);
              root = BST.insert(root, 5);
              BST.levelOrderTraversal(root);
       }
}

Time Complexity : O(n)  where n is the number of nodes.


Please comments if you like the above post or if  find the any mistake.

2 comments: