Level Order Traversal

Following figure shows the levels in a tree

level order traversal of the tree is 1, 2, 3, 4, 5

We are given the root node and we are supposed to print its level order traversal. If we closely examine the steps first we have to do is to print the root node (i.e 1 in the example) then we have to keep track of it’s child nodes. Now we have to print 2 and 3 and keep track of their child nodes. It is clear that we cannot simply use a tempnode to keep track of the values in each iteration. And we also need to keep track of the order that is 2 followed by 3 followed by 4 and so on.

So we are going to use queue data structure here. After printing a node we will enqueue its child elements to the queue. We ll repeat the same procedure until the queue becomes empty. Lets see it more clearly with code and illustration.

Code:

void levelOrder(Node root) {

Queue<Node> queue=new LinkedList<>();

queue.add(root);

while(!queue.isEmpty()){

Node tempnode = queue.remove();

System.out.print(tempnode.data+” “);

if(tempnode.left!=null)

queue.add(tempnode.left);

if(tempnode.right!=null)

queue.add(tempnode.right);

}

}

Illustration:

queue.add(root)

Dequeue the first element in queue, print it and enqueue it’s left and right child.

Dequeue 2 , print it and enqueue its left and right child. Nothing inserted here since both left and right child nodes empty for 2

Dequeue 3, print in and insert its left and right child i.e, 4 and 5

Dequeue 4, print it

Dequeue 5, print it

Related posts:

The use of surveillance cameras in public places has become a primary measure employed by many countries in order to monitor their populations, prevent crime, and act as a deterrent to terrorism…

When everyone tells you need to see a therapist and private therapy doesn’t feel like a good option, it can feel like there’s no one to help you. When you...