Converting Binary Tree to LinkedLists

Question

The problem statement is :

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

My Algorithm is to use 2 Queues and BFS to accomplish this. The code is a bit involved and I've tried to make it as simple and interesting as possible. You can easily follow it reading the comments.

//LinkListNode which will be used to create linkedlists
private static class LinkListNode<T>{
    T data;
    LinkListNode<T> next;

    public LinkListNode(T data){
        this.data = data;
    }
}

//Linked list made up of LinkListNodes
static class LinkList<T>{
    private LinkListNode<T> head;

    public void add(T toAdd){
        if(head==null){
            head = new LinkListNode<T>(toAdd);
        }else{
            LinkListNode<T> temp = head;
            while(temp.next!=null){
                temp = temp.next;
            }
            temp.next = new LinkListNode<T>(toAdd);
        }
    }

    //return true if the list is empty
    public boolean isEmpty(){
        return head==null;
    }

    //Pulls out the head Node
    //i.e. first Node in the list(Like functionality
    //of Queue)
    public T poll(){
        T data = head.data;
        head = head.next;
        return data;
    }

    //Prints out the LinkList
    public void printList(){
        LinkListNode<T> temp = head;
        if(head==null){
            System.out.println("Null List");
            return;
        }
        while(temp.next!=null){
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
        System.out.println(temp.data);
    }
}

//used to create LinkedListCollector
static class LinkListCollectorNode{
    LinkList headList;
    LinkListCollectorNode nextCollector;

    public LinkListCollectorNode(){
        headList = new LinkList();
    }
}

//LinkList collector, which will store multiple linked lists
//It can be called linkedlist of linkedlists
static class LinkListCollector{

    LinkListCollectorNode headPointer;
    LinkListCollectorNode currentPointer;

    //Adds LinkList/Nodes to the Collector
    public void add(int data){
        if(currentPointer==null && headPointer==null){
            headPointer = new LinkListCollectorNode();
            headPointer.headList.add(data);
            currentPointer = headPointer;
        }else if(currentPointer==null){
            currentPointer = new LinkListCollectorNode();
            currentPointer.headList.add(data);
        }else{
            currentPointer.headList.add(data);
        }
    }

    public void add(int...data){
        for(int i : data){
            this.add(i);
        }
    }

    //Increments the currentPointer
    public void nextCollector(){
        currentPointer.nextCollector = new LinkListCollectorNode();
        currentPointer = currentPointer.nextCollector;
    }

    //Prints all the LinkLists
    public void printListCollector(){
        LinkListCollectorNode tempNode = headPointer;

        while(tempNode!=null){
            tempNode.headList.printList();
            System.out.println();
            tempNode = tempNode.nextCollector;
        }
    }
}

//TreeNode to build a Tree
private static class TreeNode<T>{
    T data;
    TreeNode<T> left;
    TreeNode<T> right;

    public TreeNode(T data){
        this.data = data;
    }
}

static class Tree<T>{
    TreeNode<T> root;

    //Used for inorder traversal of Tree
    public void inorder(TreeNode<T> root){
        if(root.left!=null)
            inorder(root.left);
        System.out.print(root.data + " ");
        if(root.right!=null)
            inorder(root.right); 
    }
}

//1.Converts the Tree to LinkedLists depending on depth.
//2.Stores all the linkedlist in the linkedlist collector
//defined previously.
//3.Uses BFS to traverse through the tree.
//4.Uses two Queues(Simulated using LinkedList) to differentiate
//between successive levels.
public static void convertToList(Tree myTree){
    LinkList<TreeNode> one = new LinkList<TreeNode>();
    LinkList<TreeNode> two = new LinkList<TreeNode>();
    LinkList<TreeNode> currentList,otherList;
    one.add(myTree.root);
    LinkListCollector myCollector = new LinkListCollector();
    currentList = two;
    otherList = one;
    while(true){
        if(currentList==one) currentList = two;
        else if(currentList==two) currentList = one;

        if(otherList==one) otherList=two;
        else if(otherList==two) otherList=one;

        while(!currentList.isEmpty()){
            TreeNode curr = currentList.poll();
            myCollector.add((int)curr.data);
            if(curr.left!=null)
                otherList.add(curr.left);
            if(curr.right!=null)
                otherList.add(curr.right);
        }

        if(one.isEmpty() && two.isEmpty()){
            break;
        }
        myCollector.nextCollector();
    }
    myCollector.printListCollector();
}

//Main method to test the program
public static void main(String[] args) {
    Tree myTree = new Tree();
    myTree.root = new TreeNode(1);
    myTree.root.left = new TreeNode(2);
    myTree.root.right = new TreeNode(3);
    myTree.root.left.left = new TreeNode(4);
    myTree.root.left.right = new TreeNode(5);
    myTree.root.right.right = new TreeNode(7);
    myTree.root.right.left = new TreeNode(6);
    convertToList(myTree);
}

Answer 1

• The second queue is not necessary. Since the queue contains only legitimate nodes, you may use null to signal end-of-level condition:

      queue.add(root);
      queue.add(null);
  
      while (!queue.empty()) {
          TreeNode curr = queue.poll();
          if (curr != null) {
              myCollector.add(curr.data);
              if (curr.left != null)
                  queue.add(curr.left);
              if (curr.right != null)
                  queue.add(curr.right);
          } else {
              queue.add(null);
              myCollector.nextCollector();
          }
      }
  

• By poll you mean pull, right?