This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Sunday, 28 December 2014

Find Diameter Of Binary Tree


package tree;
 
import java.util.LinkedList;
import java.util.Queue;

public class FindDiameterOfBinaryTree {
 
 private Node rootNode;
 private static int maxDiameterTillNow;

 public static void main(String[] args) {
  new FindDiameterOfBinaryTree();
 }

 public FindDiameterOfBinaryTree(){
  addNode(rootNode, 100);
  addNode(rootNode, 90);
  addNode(rootNode, 150);
  addNode(rootNode, 80);
  addNode(rootNode, 91);
  addNode(rootNode, 200);
  addNode(rootNode, 70);
  addNode(rootNode, 85);
  addNode(rootNode, 93);
  addNode(rootNode, 83);
  addNode(rootNode, 92);
  addNode(rootNode, 94);
  addNode(rootNode, 81);
  addNode(rootNode, 84);
  addNode(rootNode, 95);

  printTreeLevelOrder(rootNode);
  System.out.println();
  printDiameter(rootNode);
  System.out.println(maxDiameterTillNow-1);
 }

 private int printDiameter(Node startNode) {
  return calculateDiameter(startNode);
 }

 private int calculateDiameter(Node startNode){
  if(startNode==null)
   return 0;

  int left = 1 + calculateDiameter(startNode.getLeft());
  int right = 1 + calculateDiameter(startNode.getRight());

  if(left + right >maxDiameterTillNow){
   maxDiameterTillNow = left + right;
  }
  if(left>right)
   return left;
  else
   return right;

 }

 private void printTreeLevelOrder(Node rootNode){
  if(rootNode==null)
   return;
  Queue<Node> queue = new LinkedList<Node>();
  queue.add(rootNode);

  while(!queue.isEmpty()){
   Node obj = (Node)queue.poll();
   System.out.print(obj.getData() + " ");
   if(obj.getLeft()!=null)
    queue.add(obj.getLeft());

   if(obj.getRight()!=null)
    queue.add(obj.getRight());
  }
 } 

 private void addNode(Node rootNode, int data){
  if(rootNode==null){
   Node temp1 = new Node(data);
   this.rootNode=temp1;
  }else{
   addNodeInProperPlace(rootNode, data);
  }
 }
 
 private void addNodeInProperPlace(Node rootNode, int data){ 
  if(data>rootNode.getData()){
    if(rootNode.getRight()!=null){
      addNode(rootNode.getRight(), data);
    }else{
      Node temp1 = new Node(data);
      rootNode.setRight(temp1);
    }
   }else if(data<rootNode.getData()){
     if(rootNode.getLeft()!=null){
      addNode(rootNode.getLeft(), data);
     }else{
      Node temp1 = new Node(data);
      rootNode.setLeft(temp1);
    }
  }
 }
 
}


package tree;

public class Node{
 
 private Node left;
 private Node right;
 private int data;
 
 public Node(int data){
  this.data=data;
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}

No comments:

Post a Comment