## 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;

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
makeListDFS(root, list);
return list;
}

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);
if(height == r.size()+1){
}else
ll = r.get(height-1);
return height;
}

//Using iterative BFS

//BFS using a queue
if(root==null)return r;
Node t = root;
int nextDepthAfter = 1 /*after 1 element has been dequeued */, depth = 0,
dequeued = 0; /*dequeued so far*/
while(!q.isEmpty()){
t = q.poll(); dequeued++;
if(depth == r.size()){
}else ll = r.get(depth);
if(nextDepthAfter == dequeued){ depth++; nextDepthAfter = q.size(); dequeued=0;}
}
return r;
}

//Straightforward BFS
if(root==null)return r;
Node t = root;

while(!parents.isEmpty()){
for(Node child:temp){
}
}
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");
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]