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