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