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]
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