@@ -0,0 +1,2599 @@
+package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;%0A%0Aimport com.sunny.grokkingalgorithms.ctc.c2.util.LinkedListUtil;%0Aimport com.sunny.grokkingalgorithms.ctc.c2.util.Node;%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;%0Aimport com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;%0Aimport sun.reflect.generics.tree.Tree;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.LinkedList;%0Aimport java.util.List;%0Aimport java.util.Queue;%0A%0A/**%0A * Created by sundas on 6/9/2018.%0A */%0Apublic class CreateLinkedListAtEachLevelOfBinarySearchTree %7B%0A%0A  /*%0A  Create a linked list at each level of binary search tree%0A   */%0A%0A  /**%0A   *%0A   * @param root%0A   * @return%0A   */%0A  public static List%3CNode%3E createLinkedListAtEachLevel(BinaryTreeNode root)%7B%0A    if(root == null)%7B%0A      return null;%0A    %7D%0A    /*%0A    Using level order traversal%0A     */%0A    Queue%3CBinaryTreeNode%3E queue = new LinkedList%3C%3E();%0A    List%3CNode%3E linkedLists = new ArrayList%3C%3E();%0A    queue.add(root);%0A    BinaryTreeNode levelMarker = new BinaryTreeNode();%0A    queue.add(levelMarker);%0A    Node currentLevelHead = null;%0A    Node previous = null;%0A    while(!queue.isEmpty())%7B%0A      BinaryTreeNode current = queue.poll();%0A      /*%0A      Level end logic%0A       */%0A      if(current == levelMarker)%7B%0A        /*%0A        End of level, means we have the linked list%0A         */%0A        if(currentLevelHead != null)%7B%0A          linkedLists.add(currentLevelHead);%0A        %7D%0A        /*%0A        Reset%0A         */%0A        currentLevelHead = null;%0A        previous = null;%0A        /*%0A        Prepare for next level%0A         */%0A        if(!queue.isEmpty())%7B%0A          queue.add(levelMarker);%0A        %7D%0A      %7D%0A      else%7B%0A        /*%0A        Normal processing%0A         */%0A        Node node = new Node();%0A        node.data = current.data;%0A        if(currentLevelHead == null)%7B%0A          currentLevelHead = node;%0A        %7D%0A        if(previous != null)%7B%0A          previous.next = node;%0A        %7D%0A        previous = node;%0A        /*%0A        Normal level order traversal%0A         */%0A        if(current.left != null)%7B%0A          queue.add(current.left);%0A        %7D%0A        if(current.right != null)%7B%0A          queue.add(current.right);%0A        %7D%0A      %7D%0A    %7D%0A    return linkedLists;%0A  %7D%0A%0A  /**%0A   *%0A   * @param args%0A   */%0A  public static void main(String%5B%5D args) %7B%0A    BinaryTreeNode root = TreeUtils.createBST();%0A    TreeUtils.performBfsLevelMarker(root);%0A    System.out.println(%22##################%22);%0A    List%3CNode%3E linkedLists = createLinkedListAtEachLevel(root);%0A    for(Node head : linkedLists)%7B%0A      LinkedListUtil.printLinkedList(head);%0A    %7D%0A  %7D%0A%0A%7D%0A

Convert nodes at each level of a binary tree to linked lists using level order traversal. O(n) time and O(n) space.