Diameter of Binary Tree - Better Design
You don't need to store the result in the static field diameter. Simply use the static method like that:
public class DiameterOfTree {
public static long getDiameter(BinaryTreeNode root) {
if (root != null) {
long leftDiameter = getDiameter(root.getLeft());
long rightDiameter = getDiameter(root.getRight());
long leftHeight = getHeight(root.getLeft());
long rightHeight = getHeight(root.getRight());
return Math.max(leftHeight + rightHeight + 1, Math.max(leftDiameter, rightDiameter));
}
return 0;
}
public static long getHeight(BinaryTreeNode root) {
if (root != null) {
long leftHeight = getHeight(root.getLeft());
long rightHeight = getHeight(root.getRight());
return 1 + Math.max(leftHeight, rightHeight);
}
return 0;
}
}
There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):
- The longest path passes through the root,
- The longest path is entirely contained in the left sub-tree,
- The longest path is entirely contained in the right sub-tree.
The longest path through the root is simply the sum of the heights of the left and right sub-trees (+1 for the root not necessary since the diameter of a tree with a root node and 1 left, 1 right subtree nodes will be 2), and the other two can be found recursively:
public static int getDiameter(BinaryTreeNode root) {
if (root == null)
return 0;
int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()); //Removing the +1
int leftDiameter = getDiameter(root.getLeft());
int rightDiameter = getDiameter(root.getRight());
return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}
public static int getHeight(BinaryTreeNode root) {
if (root == null)
return 0;
return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
}
Here is a solution in Java that has O(N)
time complexity.
It calculates the height in the same recursion when calculating the diameter.
Reference Link
private class HeightWrapper {
int height = 0;
}
private int getDiameter_helper(BinaryTreeNode root, HeightWrapper wrapper) {
if (root == null) {
return 0; // diameter and height are 0
}
/* wrappers for heights of the left and right subtrees */
HeightWrapper lhWrapper = new HeightWrapper();
HeightWrapper rhWrapper = new HeightWrapper();
/* get heights of left and right subtrees and their diameters */
int leftDiameter = getDiameter_helper(root.left, lhWrapper);
int rightDiameter = getDiameter_helper(root.right, rhWrapper);
/* calculate root diameter */
int rootDiameter = lhWrapper.height + rhWrapper.height + 1;
/* calculate height of current node */
wrapper.height = Math.max(lhWrapper.height, rhWrapper.height) + 1;
/* calculate the diameter */
return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
}
public int getDiameter(BinaryTreeNode root) {
HeightWrapper wrapper = new HeightWrapper();
return getDiameter_helper(root, wrapper);
}
Here is an O(n) solution with minimal changes to the accepted answer:
public static int[] getDiameter(BinaryTreeNode root) {
int[] result = new int[]{0,0}; //1st element: diameter, 2nd: height
if (root == null) return result;
int[] leftResult = getDiameter(root.getLeft());
int[] rightResult = getDiameter(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;
}
It just calculates height and diameter at the same time. And since Java does not have pass-by-reference I defined an int[] to return the result.