Problem

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

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

You can create an ArrayList of linked lists.

Approach

We can use a modified version of BFS.

1. We will add all elements in a level to a linked list.

2. Add the current linked list to the arraylist

3. Save a pointer to the current list as previous list.

4. Create a new list as current.

5. Traverse through the previous list and add all the elements to the current list

6. Repeat from step 2.

Solution

ArrayList<LinkedList<TreeNode>> createLists(TreeNode n)

{

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

  if( n== null) return lists;

  LinkedList<TreeNode> currentList = new LinkedList<TreeNode>();

  currentList.add(n);

 

  while( currentList.size() > 0 )

  {

    lists.add(currentList);

    LinkedList<TreeNode> previousList = currentList;

    currentList = new new LinkedList<TreeNode>();

    for( TreeNode p: previousList )

    {

        if( p.left ! = null )

          currentList.add(p.left);

        if( p.right ! = null )

          currentList.add(p.right);

    }

  }

  return lists;

}

Complexity

Time complexity is O(n).