package com.sunny.grokkingalgorithms.fasttrack.treesandgraphs;

import com.sunny.grokkingalgorithms.ctc.c2.util.LinkedListUtil;
import com.sunny.grokkingalgorithms.ctc.c2.util.Node;
import com.sunny.grokkingalgorithms.ctci.c4.util.BinaryTreeNode;
import com.sunny.grokkingalgorithms.ctci.c4.util.TreeUtils;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created by sundas on 6/9/2018.
 */
public class CreateLinkedListAtEachLevelOfBinarySearchTree {

  /*
  Create a linked list at each level of binary search tree
   */

  /**
   *
   * @param root
   * @return
   */
  public static List<Node> createLinkedListAtEachLevel(BinaryTreeNode root){
    if(root == null){
      return null;
    }
    /*
    Using level order traversal
     */
    Queue<BinaryTreeNode> queue = new LinkedList<>();
    List<Node> linkedLists = new ArrayList<>();
    queue.add(root);
    BinaryTreeNode levelMarker = new BinaryTreeNode();
    queue.add(levelMarker);
    Node currentLevelHead = null;
    Node previous = null;
    while(!queue.isEmpty()){
      BinaryTreeNode current = queue.poll();
      /*
      Level end logic
       */
      if(current == levelMarker){
        /*
        End of level, means we have the linked list
         */
        if(currentLevelHead != null){
          linkedLists.add(currentLevelHead);
        }
        /*
        Reset
         */
        currentLevelHead = null;
        previous = null;
        /*
        Prepare for next level
         */
        if(!queue.isEmpty()){
          queue.add(levelMarker);
        }
      }
      else{
        /*
        Normal processing
         */
        Node node = new Node();
        node.data = current.data;
        if(currentLevelHead == null){
          currentLevelHead = node;
        }
        if(previous != null){
          previous.next = node;
        }
        previous = node;
        /*
        Normal level order traversal
         */
        if(current.left != null){
          queue.add(current.left);
        }
        if(current.right != null){
          queue.add(current.right);
        }
      }
    }
    return linkedLists;
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {
    BinaryTreeNode root = TreeUtils.createBST();
    TreeUtils.performBfsLevelMarker(root);
    System.out.println("##################");
    List<Node> linkedLists = createLinkedListAtEachLevel(root);
    for(Node head : linkedLists){
      LinkedListUtil.printLinkedList(head);
    }
  }

}

@@ -2222,16 +2222,1153 @@
 s;%0A  %7D%0A%0A
+  /**%0A   *%0A   * @param root%0A   * @param linkedLists%0A   * @param level%0A   */%0A  public static void createLinkedListAtEachLevelUsingDFS(BinaryTreeNode root,%0A                                                         List%3CLinkedList%3E linkedLists,%0A                                                         int level)%7B%0A    if(root == null)%7B%0A      return;%0A    %7D%0A    /*%0A    The idea is that each level represents an index on the linkedLists. The linked list cannot%0A    be null. We we visit left or right child , we essentially increase the level count by 1%0A     */%0A    if(level == linkedLists.size())%7B%0A      /*%0A      New level%0A       */%0A      LinkedList linkedList = new LinkedList();%0A      linkedList.add(root.data);%0A      linkedLists.add(linkedList);%0A    %7D%0A    else%7B%0A      /*%0A      The level is already contained in the list, just fetch it at the index%0A       */%0A      LinkedList linkedList = linkedLists.get(level);%0A      if(linkedList != null)%7B%0A        linkedList.add(root.data);%0A      %7D%0A    %7D%0A    createLinkedListAtEachLevelUsingDFS(root.left,linkedLists,level+1);%0A    createLinkedListAtEachLevelUsingDFS(root.right,linkedLists,level+1);%0A  %7D%0A%0A
   /**%0A  
@@ -3722,15 +3722,279 @@
 ;%0A    %7D%0A
+    System.out.println(%22#########%22);%0A    List%3CLinkedList%3E lists = new ArrayList%3C%3E();%0A    createLinkedListAtEachLevelUsingDFS(root, lists,0);%0A    for(LinkedList linkedList : lists)%7B%0A      System.out.println(linkedList);%0A      System.out.println(%22---------%22);%0A    %7D%0A
   %7D%0A%0A%7D%0A

Create linked lists from nodes at each level using DFS.