Problem

Given a binary tree, create a linked list of all nodes at each level of binary tree using recursion.

If there are n levels, there will be n linked lists.

You can create an ArrayList of linked lists.

Approach

We will create an ArrayList of linked lists. We will pass in the array list to the method along with a level attribute. 

If the size of arraylist is equal to the level, the level has not been visited before and we will create a new linked list and add elements.

If the size of arraylist is greater that the level, the level has been visited before and we will add elements.

Solution

void createLists(TreeNode n, ArrayList<LinkedList<TreeNode>> lists, int level)

{

  if( n== null) return;

  LinkedList<TreeNode> list;

  if( lists.size() == level )

  {

    list = new LinkedList<TreeNode>();

    lists.add(list);

  }

  else{

    list = lists.get(level);

  }

  list.add(n);

  createLists(n.left, lists, level + 1);

  createLists(n.right, lists, level + 1);

}

We can invoke this method as:

ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();

createLists(root, lists, 0);

Complexity

Time complexity will be O(N).

Extra O(log n) will be taken for recursion.