Q12: How do you compute the Diameter of a Binary Tree?
The diameter is the length of the longest path between any two nodes in a tree (which may or may not pass through root). Compute the height of left and right subtrees recursively: at each node, currentDiameter = leftHeight + rightHeight. Maintain a global max variable.
Binary Tree Diameter Solution
public class TreeDiameter {
private static int maxDiameter = 0;
public static int diameterOfBinaryTree(TreeNode root) {
maxDiameter = 0;
getHeight(root);
return maxDiameter;
}
private static int getHeight(TreeNode node) {
if (node == null) return 0;
int left = getHeight(node.left);
int right = getHeight(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return 1 + Math.max(left, right);
}
}💡 Updates global maximum path length while calculating subtree heights recursively.
Key Takeaways
- Diameter at any node =
leftHeight + rightHeight. - Returns tree height to parent callers while tracking maximum diameter globally.
Knowledge Check
Does the longest diameter path in a binary tree ALWAYS pass through the root node?