Tree: Level Order Traversal Hackerrank Solution

Definition: In the Level Order Traversal, the binary tree is traversed level-wise starting from the first to last level sequentially.

Consider the following binary tree image:

The Level Order Traversal of the above Binary Tree will be: 10 4 8 50 24 5 12 18.

Algorithm:

 The Level Order Traversal can be implemented efficiently using a Queue.
1.Create an empty queue q.
2.Push the root node of tree to q. That is, q.push(root).
3.Loop while the queue is not empty:
4.Pop the top node from queue and print the node.
5.Enqueue node's children (first left then right children) to q
6.Repeat the process until queue is not empty.

Problem:

You are given a pointer to the root of a binary tree. You need to print the level order traversal of this tree. In level order traversal, we visit the nodes level by level from left to right. You only have to complete the function. For example:

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  

For the above tree, the level order traversal is 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Input Format

You are given a function,

void levelOrder(Node  root) {

}

Constraints

1 <= Nodes in the tree <= 500

Output Format

Print the values in a single line separated by a space.

Sample Input

     1
      \
       2
        \
         5
        /  \
       3    6
        \
         4  

Sample Output

1 2 5 3 6 4

Explanation

We need to print the nodes level by level. We process each level from left to right.
Level Order Traversal: 1 -> 2 -> 5 -> 3 -> 6 -> 4.

Code:

package tree;

import java.util.LinkedList;
import java.util.Queue;

public class LevelOrderTraversal {
	public static void level(Node root) {
		if(root == null)
			return;
		
		Queue<Node> qu = new LinkedList<>();
		qu.add(root);
		while(!qu.isEmpty()) {
			Node temp = qu.remove();
			System.out.print(temp.data + " ");
			if(temp.left != null)
				qu.add(temp.left);
			if(temp.right != null)
				qu.add(temp.right);
				
		}
		}

	public static void main(String[] args) {
		Node root= new Node(10); 
        root.left= new Node(4); 
      root.right= new Node(8); 
      root.left.left= new Node(50); 
     root.left.right= new Node(24); 
     root.left.left.right = new Node(18);
     root.right.left = new Node(5);
     root.right.right = new Node(12);
     level(root);

	}

}
Output:
10 4 8 50 24 5 12 18 

Time Complexity: O(N), where N is the number of nodes in the Tree.
Auxiliary Space: O(N).

Hope you all get the concept of level order traversal using queue.

In the next blog we will see other tree implementation using both methods i.e iterative and recursive in java.

So till then Bye Bye…!

Happy Coding..!

Thank You…!



Categories: HackerRank Questions, JAVA, Uncategorized

Tags: , , , , , ,

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: