5
\$\begingroup\$

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);
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$
  • 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?

\$\endgroup\$
3
  • \$\begingroup\$ No, by poll, I mean poll. Since that's what its called in Java's LinkedList API \$\endgroup\$ Jan 18, 2016 at 3:50
  • \$\begingroup\$ @MayurKulkarni I be damned! You are right. But why do they do this? \$\endgroup\$
    – vnp
    Jan 18, 2016 at 4:01
  • \$\begingroup\$ Haha, I totally understand this feeling, crazy creators :) \$\endgroup\$ Jan 18, 2016 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.