Nov 16, 2013

Textual description of firstImageUrl

Iterative level order traversal of binary tree in Java

Level order traversal is one of common interview question and it creates foundation of various other problems.In order to visit tree nodes in level order fashion, we need to store nodes in a Queue instead of stack (since Queue has FIFO property).Consider following tree and its level order traversal node sequence.

Level order traversal :-   12 23 18 11 43 12 27 56 78 32 98

Algorithm:- 
1. Do check for empty tree(root not null), if root is not null, enqueue root into queue.
2. Loop until queue is not empty
       Dequeue node from queue and check for left and right child, if exist enqueues them
        process dequeued node and repeat step 2.
3.  Exit loop when queue becomes empty

Sample code for iterative level order traversal :- 
public void iterativelevelOrderTraversal(Node root) {
 /* java.util.ArrayDeque */
 Queue<Node> queue = new ArrayDeque<>();
 if (root != null) {
  queue.add(root);
  while (!queue.isEmpty()) {
   /* Dequeue form queue */
   root = queue.remove();
   Node lc = root.leftChild;
   Node rc = root.rightChild;
   if (lc != null) {
    queue.add(lc);
   }
   if (rc != null) {
    queue.add(rc);
   }
   System.out.print(root.data + " ");
  }
 }
}

Complete sample program for iterative level order traversal 

package com.devinline.trees;

import java.util.ArrayDeque;
import java.util.Queue;

public class LevelOrderTraversal {
 public void iterativelevelOrderTraversal(Node root) {
  /* java.util.ArrayDeque */
  Queue<Node> queue = new ArrayDeque<>();
  if (root != null) {
   queue.add(root);
   while (!queue.isEmpty()) {
    /* Dequeue form queue */
    root = queue.remove();
    Node lc = root.leftChild;
    Node rc = root.rightChild;
    if (lc != null) {
     queue.add(lc);
    }
    if (rc != null) {
     queue.add(rc);
    }
    System.out.print(root.data + " ");
   }
  }
 }

 public static void main(String[] args) {
  LevelOrderTraversal lo = new LevelOrderTraversal();
  Node root = lo.new BinaryTree().createTree();
  System.out.print("Level order traversal is : ");
  lo.iterativelevelOrderTraversal(root);
 }

 class BinaryTree {
  Node root;

  public BinaryTree() {
   root = null;
  }

  public Node createTree() {
   if (root == null) {
    root = new Node(12);
   }
   root.setLeftChild(new Node(23));
   root.setRightChild(new Node(18));
   root.getLeftChild().setLeftChild(new Node(11));
   root.getLeftChild().setRightChild(new Node(43));
   root.getRightChild().setRightChild(new Node(27));
   root.getRightChild().setLeftChild(new Node(12));
   root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
   root.getLeftChild().getLeftChild().setRightChild(new Node(78));
   root.getRightChild().getLeftChild().setRightChild(new Node(98));
   root.getRightChild().getLeftChild().setLeftChild(new Node(32));
   return root;
  }
 }

 class Node {

  private int data;
  private Node leftChild;
  private Node rightChild;

  public Node(int data) {
   this.data = data;
   leftChild = null;
   rightChild = null;
  }

  public int getData() {
   return data;
  }

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

  public Node getLeftChild() {
   return leftChild;
  }

  public void setLeftChild(Node leftChild) {
   this.leftChild = leftChild;
  }

  public Node getRightChild() {
   return rightChild;
  }

  public void setRightChild(Node rightChild) {
   this.rightChild = rightChild;
  }
 }
}
=========Sample output==========
Level order traversal is : 12 23 18 11 43 12 27 56 78 32 98
==============================
Location: Hyderabad, Telangana, India