Definition
- Diameter – the longest path between any two nodes in a binary tree, measured in edges.
- Key insight – for any node, the longest path through it equals the depth of its left subtree plus the depth of its right subtree.
- Efficient approach – a single post-order traversal returns each subtree's depth while updating a shared maximum with the candidate diameter.
- Complexity – O(n) time, O(h) space for the recursion stack.
- Convention – in edges:
leftDepth + rightDepth; in nodes: add one.
Think of the National Bank of India's org chart. Management wants the longest chain of relationships between any two employees, going up to some common manager and back down the other side. At each manager, the longest such chain through them is how deep their left team goes plus how deep their right team goes. The overall longest chain across all managers is the diameter.
Understanding the Concepts
What is the diameter of a binary tree?
The diameter is the number of edges on the longest path between any two nodes in the tree. This path may or may not pass through the root. It could connect two nodes deep within one subtree through a mid-level ancestor.
package com.bank.model;
public class OrgNode {
public String title;
public OrgNode left;
public OrgNode right;
public OrgNode(String title) {
this.title = title;
}
}
How does the efficient single-pass solution work?
Write a helper that returns the depth of a subtree. Before returning, update a shared maximum with the candidate diameter at the current node: leftDepth + rightDepth. The helper then returns 1 + max(leftDepth, rightDepth) as the node's own depth.
package com.bank.service;
import com.bank.model.OrgNode;
public class TreeDiameter {
private int maxDiameter = 0;
public int diameter(OrgNode root) {
maxDiameter = 0;
depth(root);
return maxDiameter;
}
private int depth(OrgNode node) {
if (node == null) return 0;
int left = depth(node.left);
int right = depth(node.right);
// Update diameter: longest path through this node
maxDiameter = Math.max(maxDiameter, left + right);
// Return depth of this subtree
return 1 + Math.max(left, right);
}
public static void main(String[] args) {
// CEO
// / \
// VP1 VP2
// / \
// DIR1 DIR2
// /
// MGR1
OrgNode ceo = new OrgNode("CEO");
OrgNode vp1 = new OrgNode("VP1");
OrgNode vp2 = new OrgNode("VP2");
OrgNode dir1 = new OrgNode("DIR1");
OrgNode dir2 = new OrgNode("DIR2");
OrgNode mgr1 = new OrgNode("MGR1");
ceo.left = vp1; ceo.right = vp2;
vp1.left = dir1; vp2.right = dir2;
dir1.left = mgr1;
TreeDiameter td = new TreeDiameter();
System.out.println("Diameter: " + td.diameter(ceo) + " edges");
}
}
Diameter: 5 edges
Why is the naive approach quadratic?
The naive approach computes depth independently at every node, which repeats work. For a skewed tree this becomes O(n^2). Fusing the depth computation with the diameter update makes each node's depth computed exactly once, keeping the total at O(n).
// NAIVE O(n^2): recomputes depth at every node
public int diameterNaive(OrgNode root) {
if (root == null) return 0;
int throughRoot = depthSeparate(root.left) + depthSeparate(root.right);
int leftDiam = diameterNaive(root.left);
int rightDiam = diameterNaive(root.right);
return Math.max(throughRoot, Math.max(leftDiam, rightDiam));
}
private int depthSeparate(OrgNode node) {
if (node == null) return 0;
return 1 + Math.max(depthSeparate(node.left), depthSeparate(node.right));
}
What about the counting convention: edges vs nodes?
Some problems define diameter in nodes (count the nodes on the path) rather than edges. In edges, the formula is leftDepth + rightDepth. In nodes, it is leftDepth + rightDepth + 1. Always state which convention you are using.
// Edges: leftDepth + rightDepth
maxDiameter = Math.max(maxDiameter, left + right);
// Nodes: leftDepth + rightDepth + 1
maxDiameter = Math.max(maxDiameter, left + right + 1);
// A single node: diameter in edges = 0, diameter in nodes = 1
Why can the longest path skip the root?
The longest path does not have to go through the root. It could connect two nodes deep within the left subtree through a mid-level node. Evaluating the candidate diameter at every node catches paths that never touch the root.
// A
// /
// B
// / \
// C D
// / \
// E F
//
// Longest path: E -> C -> B -> D -> F = 4 edges
// This path goes through B, not through A
What are the edge cases?
Empty tree (diameter 0), single node (diameter 0), and a completely linear tree (skewed) where the diameter equals the number of edges.
package com.bank.service;
import com.bank.model.OrgNode;
public class DiameterEdgeCases {
public static void main(String[] args) {
TreeDiameter td = new TreeDiameter();
// Empty tree
System.out.println("Empty: " + td.diameter(null));
// Single node
System.out.println("Single: " + td.diameter(new OrgNode("CEO")));
// Skewed: CEO -> VP -> DIR -> MGR
OrgNode skewed = new OrgNode("CEO");
skewed.left = new OrgNode("VP");
skewed.left.left = new OrgNode("DIR");
skewed.left.left.left = new OrgNode("MGR");
System.out.println("Skewed: " + td.diameter(skewed));
}
}
Empty: 0
Single: 0
Skewed: 3
What is the relationship to Maximum Path Sum?
The diameter and maximum path sum problems share the same structure: a post-order recursion that returns one value to the parent while updating a global with a different value. In diameter, you return depth and update a sum of depths. In maximum path sum, you return the best single-branch gain and update a global with the best bending path. Recognizing this shared pattern is a senior-level observation.
// Same structure in both problems:
private int helper(Node node) {
if (node == null) return BASE;
int left = helper(node.left);
int right = helper(node.right);
globalMax = Math.max(globalMax, COMBINE(left, right, node));
return PROPAGATE(left, right, node);
}
What should a senior engineer know?
A senior engineer should be able to derive the O(n) solution by recognizing that the naive approach recomputes heights and explaining exactly where the repeated work happens. The dual role of the recursive helper, returning depth while updating diameter, is the key optimization.
In production at National Bank of India, this analysis runs on the org hierarchy to find the longest escalation chain between any two employees. An over-long chain slows approvals, so the service reports the diameter to the org-structure dashboard.
// Report diameter as an org health metric
int chainLength = new TreeDiameter().diameter(orgRoot);
if (chainLength > MAX_ACCEPTABLE_CHAIN) {
alertService.send("Org diameter " + chainLength
+ " exceeds threshold " + MAX_ACCEPTABLE_CHAIN);
}
Visual Overview
Post-Order Depth + Diameter Fusion
CEO depth=3
/ \ diameter through CEO = 3 + 2 = 5
VP1 VP2 depth=2, depth=2
/ \
DIR1 DIR2 depth=1, depth=1
/
MGR1 depth=0 (leaf returns 0+1=1 to parent)
maxDiameter tracks: 0 → 0 → 0 → 2 → 5
Final answer: 5 edges
Path that skips the root:
A (depth=4)
/
B (depth=3)
/ \
C D Diameter through B = 2 + 2 = 4
/ \
E F
Longest path: E → C → B → D → F (4 edges)
Goes through B, not through A.
Key Takeaway
The diameter of a binary tree is the longest path between any two nodes measured in edges, and the key insight is that for any node, the longest path through it is the depth of its left subtree plus the depth of its right subtree. This lets you compute the diameter during a single depth calculation rather than separately, which is what makes the solution linear instead of quadratic.
The helper function returns the depth of a subtree to its parent, and the fusion happens just before it returns: it updates a shared maximum with leftDepth + rightDepth at the current node. Because every node gets evaluated as a potential turning point of the longest path, the algorithm correctly captures paths that do not pass through the root.
Be precise about the counting convention. Measuring in edges means leftDepth + rightDepth; measuring in nodes means adding one. A single node has diameter zero in edges and one in nodes. Confusing these is the classic mistake on this problem.
In our banking system at National Bank of India, we use this on the org hierarchy to find the longest escalation chain between any two employees. An over-long chain slows approvals, and the longest chain often runs between two deep branches through a mid-level manager rather than through the CEO. Reporting the diameter as an org health metric helps management spot and fix structural bottlenecks.
Remember one sentence: fuse depth computation with diameter tracking in one post-order pass; leftDepth + rightDepth at each node is the candidate diameter in edges.
---