Find diameter of Binary Tree.
What is Diameter of a Binary Tree?
A longest path or route between any two nodes in a tree is called as Diameter/Width of binary tree.
The diameter of tree may or may not pass through the root. The diagram below shows two trees each with diameter 7, diameter are shaded with blue nodes.
Diameter of node = height of Left sub tree of node + height of Right sub tree of node + 1 (node itself).
Solution
We will discuss 3 ways of finding diameter of Binary tree. Lets start with simple approach,
1. By using Global variable
In this approach, we will check the diameter of each node of a tree and store it in variable "diameter".
For each node, calculate diameter and if it is larger than static variable "diameter", then update "diameter" otherwise not.
At end of the process, static variable "diameter" will contain maximum distance between any of two nodes in our binary tree.
2. By computing height and diameter of each node.
In this approach, we will not use the global variable,Instead, we will check, which is maximum between,1. Diameter of a Node,
2. Diameter of a left sub tree of Node,
3. Diameter of a right sub tree of Node,
Whichever is maximum among this 3, that will be diameter of that node and return it to next recursive call.
At each node of binary tree, above comparison is done and maximum diameter count found at that node will be returned.
In this way, by returning the maximum diameter in each iteration, it will help preserving the maximum diameter found at any node in between the tree.
3. By computing height and diameter of each node in optimized way.
In this approach, Every node will return the two information in the same iteration,
1. height of that node and
2. diameter of tree with respect to that node.
This way it will save 2 extra iteration that need to be done in Approach 2.
Diameter of Binary Tree in Java (Approach 1)
package javabypatel.tree;
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, 95);
addNode(rootNode, 70);
addNode(rootNode, 92);
addNode(rootNode, 60);
addNode(rootNode, 94);
getDiameterOfBinaryTreeUsingGlobalVariable(rootNode);
System.out.println(maxDiameterTillNow);
}
private int getDiameterOfBinaryTreeUsingGlobalVariable(Node startNode){
if(startNode==null)
return 0;
int leftHeight = getDiameterOfBinaryTreeUsingGlobalVariable(startNode.getLeft()); // Height of Left Subtree
int rightHeight = getDiameterOfBinaryTreeUsingGlobalVariable(startNode.getRight()); // Height of Right Subtree
if(leftHeight + rightHeight + 1 > maxDiameterTillNow){ // + 1 for node itself
maxDiameterTillNow = leftHeight + rightHeight + 1;
}
if(leftHeight>rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
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 javabypatel.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;
}
}
Diameter of Binary Tree in Java (Approach 2)
package javabypatel.tree;
public class FindDiameterOfBinaryTree {
private Node rootNode;
public static void main(String[] args) {
new FindDiameterOfBinaryTree();
}
public FindDiameterOfBinaryTree(){
addNode(rootNode, 100);
addNode(rootNode, 90);
addNode(rootNode, 150);
addNode(rootNode, 80);
addNode(rootNode, 95);
addNode(rootNode, 70);
addNode(rootNode, 92);
addNode(rootNode, 60);
addNode(rootNode, 94);
System.out.println(getDiameterOfBinaryTree(rootNode));
}
private int getDiameterOfBinaryTree(Node node){
if(node == null){
return 0;
}
int leftSubtreeHeight = height(node.getLeft());
int rightSubtreeHeight = height(node.getRight());
int diameterOfNode = leftSubtreeHeight + rightSubtreeHeight + 1;
int leftDiameter = getDiameterOfBinaryTree(node.getLeft());
int rightDiameter = getDiameterOfBinaryTree(node.getRight());
return max(diameterOfNode, max(leftDiameter, rightDiameter));
}
private int height(Node node){
if( node == null){
return 0;
}
int lHeight = height(node.getLeft());
int rHeight = height(node.getRight());
return (max(lHeight , rHeight)+1);
}
private int max(int a, int b){
return a > b ? a : b;
}
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);
}
}
}
}
Diameter of Binary Tree in Java (Approach 3)
package javabypatel.tree;
public class FindDiameterOfBinaryTree {
private Node rootNode;
public static void main(String[] args) {
new FindDiameterOfBinaryTree();
}
public FindDiameterOfBinaryTree(){
addNode(rootNode, 100);
addNode(rootNode, 90);
addNode(rootNode, 150);
addNode(rootNode, 80);
addNode(rootNode, 95);
addNode(rootNode, 70);
addNode(rootNode, 92);
addNode(rootNode, 60);
addNode(rootNode, 94);
System.out.println(getDiameterOfBinaryTreeOptimizedSolution(rootNode)[0]);
}
public static int[] getDiameterOfBinaryTreeOptimizedSolution(Node root) {
//0th element is diameter and 1st element is height
int[] result = new int[]{0,0};
if (root == null)
return result;
int[] leftResult = getDiameterOfBinaryTreeOptimizedSolution(root.getLeft());
int[] rightResult = getDiameterOfBinaryTreeOptimizedSolution(root.getRight());
int height = Math.max(leftResult[1], rightResult[1]) + 1;
int rootDiameter = leftResult[1] + rightResult[1] + 1;
int leftDiameter = leftResult[0];
int rightDiameter = rightResult[0];
result[0] = Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
result[1] = height;
return result;
}
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);
}
}
}
}
You may also like to see
Find Kth largest element in BST(Binary Search Tree)
Serialize and Deserialize a Binary Tree
Rotate matrix by 90 degree
Print nodes at K distance from Leaf node in Binary tree.
Print Matrix Diagonally OR Diagonal order of Matrix.
Count number of Bits to be flipped to convert A to B
Enjoy !!!!
If you find any issue in post or face any error while implementing, Please comment.
No comments:
Post a Comment