Level order traversal without a queue

Problem

Given a binary tree print the node values in level order without using a queue.

Solution

We will use a map whose key is the level and value is the list of nodes. We will call a recursive function on the root passing a blank map and a level value of 1. At each node it will check whether the current level as a key is present in the map or not. If it is present it add the current node's value to the corresponding list. If the key is not present then it adds the level as key and a list containing current node as value. Then call the recursive function to its children with level value increased by one. When it hits null nodes, it returns. After this recursive method ends we have all the level wise data in the map. We will start from level 1 and print the data from its value list and keep on increasing the level till that level exists in the map. The space complexity for this solution is O(n) and time complexity is O(n).

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class LevelOrderWithoutQueue
{

 /**
  * @param args
  */
 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(8);
  Node g = new Node(6);
  Node h = new Node(7);
  a.left = b;
  a.right = c;
  b.left = d;
  b.right = e;
  c.right = f;
  f.left = g;
  f.right = h;
  printLevelOrder(a);
 }

 private static void printLevelOrder(Node a)
 {
  HashMap < Integer, List < Integer > > levelMap = 
   new HashMap < Integer, List < Integer > >();
  printLevelOrder(a, 1, levelMap);
  int level = 1;
  while (true)
  {
   List < Integer > list = levelMap.get(level);
   if (list == null)
    break;
   System.out.println(list);
   level++;
  }
 }

 private static void printLevelOrder(Node a, int level,
   HashMap < Integer, List < Integer > > levelMap)
 {
  if (a == null)
   return;
  List < Integer > list = levelMap.get(level);
  if (list == null)
  {
   list = new ArrayList < Integer > ();
   list.add(a.value);
   levelMap.put(level, list);
  } else
  {
   list.add(a.value);
  }
  printLevelOrder(a.left, level + 1, levelMap);
  printLevelOrder(a.right, level + 1, levelMap);
 }

 static class Node
 {
  Node left;
  Node right;
  int value;

  public Node(int value)
  {
   this.value = value;
  }
 }

}

Index