Diameter of a Binary Tree is path with maximum count of edges between two Tree Nodes. Given a Binary Tree, find and return the Diameter of the Tree.
| Input Parameters |
Expected outputs |
Find diameter of above tree.
|
Max Diameter: 8
|
| Initialize a variable maximumDistance to hold the diameter.
|
| Call updateMaxDistance().
|
| Return maximumDistance.
|
| If TreeNode is null return 0.
|
| Set leftDepth by calling updateMaxDistanc() with TreeNode’s left child.
|
| Set rightDepth by calling updateMaxDistanc() with TreeNode’s right child.
|
| Set currentMaxDistance to (leftDepth + rightDepth).
|
| If (currentMaxDistance > maximumDistance) set maximumDistance to currentMaxDistance.
|
| Initialize a variable currentMaxDepth of type integer.
|
| If leftDepth > rightDepth, set currentMaxDepth= leftDepth.
|
| If rightDepth > leftDepth, set currentMaxDepth= rightDepth.
|
| Return currenMaxDepth+1.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
Note: for easy reference BinTreeNode is included as internal class in program below. Ideally it should be in a separate file.
public class BinTreeMaxDiameter {
private int maxDistanceBetween2Nodes=0;
public int finddMaxDiameter(BinTreeNode root) {
updateMaxDistance(root);
return maxDistanceBetween2Nodes;
}
public int updateMaxDistance(BinTreeNode node) {
if (node==null) {
return 0;
}
int leftMaxDepth=updateMaxDistance(node.getLeftChild());
int rightMaxDepth=updateMaxDistance(node.getRightChild());
int currenMaxDistance=leftMaxDepth+rightMaxDepth;
if (currenMaxDistance > maxDistanceBetween2Nodes ) {
maxDistanceBetween2Nodes=currenMaxDistance;
}
int currenMaxDepth=0;
if (leftMaxDepth >rightMaxDepth ) {
currenMaxDepth=leftMaxDepth;
}else {
currenMaxDepth=rightMaxDepth;
}
return currenMaxDepth+1;
}
public static void main(String[] args) {
/**********************
Test cases given below:
**********************/
int retVal=0;
try {
BinTreeMaxDiameter dia=new BinTreeMaxDiameter();
BinTreeNode root=dia.new BinTreeNode(4);
//Left L1 Children
root.setLeftChild(dia.new BinTreeNode(5));
root.setRightChild(dia.new BinTreeNode(7));
//Left L2 Children
root.getLeftChild().setLeftChild(dia.new BinTreeNode(6));
root.getLeftChild().setRightChild(dia.new BinTreeNode(78));
//Left L3 Children
root.getLeftChild().getLeftChild().setLeftChild(dia.new BinTreeNode(33));
//Right L2 Children
root.getRightChild().setLeftChild(dia.new BinTreeNode(14));
//Right L3 Children
root.getRightChild().getLeftChild().setLeftChild(dia.new BinTreeNode(8));
root.getRightChild().getLeftChild().setRightChild(dia.new BinTreeNode(16));
//Right L3 Children
root.getRightChild().getLeftChild().getRightChild().setLeftChild(dia.new BinTreeNode(18));
//Right L4 Children
root.getRightChild().getLeftChild().getRightChild().getLeftChild().setLeftChild(dia.new BinTreeNode(9));
retVal=dia.finddMaxDiameter(root);
System.out.println("Max Diameter: "+retVal);
}catch (Exception exception) {
System.out.print("Exception: "+ exception);
exception.printStackTrace();
}
}
public class BinTreeNode {
private BinTreeNode leftNode=null;
private BinTreeNode rightNode=null;
private int nodeData=0;
public BinTreeNode(int data) {
nodeData=data;
}
public BinTreeNode getLeftChild() {
return leftNode;
}
public void setLeftChild(BinTreeNode leftNode) {
this.leftNode = leftNode;
}
public BinTreeNode getRightChild() {
return rightNode;
}
public void setRightChild(BinTreeNode rightNode) {
this.rightNode = rightNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
}