Sunday, December 28, 2014

Creating a seperate LinkedList for all the nodes at each depth of a given binary tree

Q. 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).

Algorithm:

We can do this using Depth First Traversal or Breadth First Traversal

Source:

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

public class Code{
    
    public class Node{
        int value;
        Node left, right;
        Node(){}
        Node(int value){this.value = value;}
        Node(int value, Node left, Node right){
            this.value = value;
            this.left = left;
            this.right = right;
        }
        
        @Override
        public String toString(){
            return "Value: "+value;
        }
    }
    
    Node root; 
    
        //Using recursive DFS
    ArrayList<LinkedList<Node>> getNodesAtDepthsDFS(){
        ArrayList<LinkedList<Node>> list = new ArrayList<>();
        makeListDFS(root, list);
        return list;
    }
    
    int makeListDFS(Node node, ArrayList<LinkedList<Node>> r){
        if(node == null) return 0;
        int left = makeListDFS(node.left, r)+1; 
        int right = makeListDFS(node.right, r)+1;   
        int height = Math.max(left, right);
        LinkedList<Node> ll; 
        if(height == r.size()+1){
            ll = new LinkedList<>();
            r.add(ll);
        }else
            ll = r.get(height-1);
        ll.add(node);
        return height;
    }
    
    //Using iterative BFS 
    
    //BFS using a queue
    ArrayList<LinkedList<Node>> getNodesAtDepthsBFS(){ 
        ArrayList<LinkedList<Node>> r = new ArrayList<>();
        if(root==null)return r;
        Node t = root;
        Queue<Node> q = new LinkedList<>();
        q.add(t);
        int nextDepthAfter = 1 /*after 1 element has been dequeued */, depth = 0,
            dequeued = 0; /*dequeued so far*/
        while(!q.isEmpty()){    
            t = q.poll(); dequeued++;  
            LinkedList<Node> ll;
            if(depth == r.size()){
                ll = new LinkedList<>();
                r.add(ll);
            }else ll = r.get(depth); 
            ll.add(t);
            if(t.left!=null){q.add(t.left);}
            if(t.right!=null){q.add(t.right);}
            if(nextDepthAfter == dequeued){ depth++; nextDepthAfter = q.size(); dequeued=0;}
        }
        return r;
    } 
    
    //Straightforward BFS
    ArrayList<LinkedList<Node>> getNodesAtDepthsBFS2(){
        ArrayList<LinkedList<Node>> r = new ArrayList<>();
        if(root==null)return r;
        Node t = root;
        LinkedList<Node> parents = new LinkedList<>();
        parents.add(t); 
        
        while(!parents.isEmpty()){
            LinkedList<Node> temp = parents; 
            r.add(parents);
            parents = new LinkedList<>();
            for(Node child:temp){
                 if(child.left!=null)parents.add(child.left);
                 if(child.right!=null)parents.add(child.right); 
            } 
        }
        return r; 
    }
    
    //Other functions
    void makeCustom(){
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.right = new Node(4);
        root.right.left = new Node(5);
        root.right.left.right = new Node(6);
    }
    
    void printTree(String string){
        System.out.println(string);
        inorder(root);
    }
    
    void inorder(Node node){
        if(node==null)return;
        inorder(node.left);
        System.out.println(node.value);
        inorder(node.right);
    }
    
    //Test
    public static void main(String[] args){ 
        Code tree = new Code();
         
        //DFS
        tree.makeCustom();
        tree.printTree("Printing tree contents"); 
        
        System.out.println("\nUsing DFS");
        ArrayList<LinkedList<Node>> r = tree.getNodesAtDepthsBFS(); 
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i)); 
        
        //BFS Using a queue
        System.out.println("\nBFS using a queue");
        r = tree.getNodesAtDepthsBFS(); 
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i));  
        
        //BFS - StraightForward method
        System.out.println("\nBFS - Method 2");
        r = tree.getNodesAtDepthsBFS2();
        for(int i=0;i<r.size();++i) System.out.println("Depth = "+i+" Node: "+r.get(i)); 
    }
}

Output:

Printing tree contents
2
4
1
5
6
3

Using DFS
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

BFS using a queue
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

BFS - Method 2
Depth = 0 Node: [Value: 1]
Depth = 1 Node: [Value: 2, Value: 3]
Depth = 2 Node: [Value: 4, Value: 5]
Depth = 3 Node: [Value: 6]

No comments:

Post a Comment