Definition
- Diameter (in nodes) – the number of nodes on the longest path between any two nodes in the tree.
- Key insight – the longest path through any node is
leftHeight + rightHeight + 1(the left depth, plus the node itself, plus the right depth). - Efficient approach – a single post-order traversal returns height while updating a shared maximum.
- Complexity – O(n) time, O(h) space.
- Convention – in nodes:
leftHeight + rightHeight + 1; in edges:leftHeight + rightHeight.
At the National Bank of India, the approval hierarchy is a tree. Management wants the longest possible escalation path between any two desks, measured in number of desks visited. That longest stretch might not go through the head office at all; it could run up one branch and down another. At every desk, the span is how deep the left reports go plus one (the desk itself) plus how deep the right reports go.
Understanding the Concepts
What is tree diameter counted in nodes?
The diameter is the number of nodes on the longest path between any two nodes. This differs from the edge-counted version by exactly one. The path can start and end anywhere and does not need to pass through the root.
package com.bank.model;
public class DeskNode {
public String deskId;
public DeskNode left;
public DeskNode right;
public DeskNode(String deskId) {
this.deskId = deskId;
}
}
How does the efficient post-order solution work?
A helper returns the height of a subtree. Before returning, it updates a shared maximum with leftHeight + rightHeight + 1, which is the candidate diameter through this node counted in nodes.
package com.bank.service;
import com.bank.model.DeskNode;
public class TreeDiameterNodes {
private int maxDiameter = 0;
public int diameter(DeskNode root) {
maxDiameter = 0;
height(root);
return maxDiameter;
}
private int height(DeskNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
// Candidate diameter in nodes
maxDiameter = Math.max(maxDiameter, left + right + 1);
return 1 + Math.max(left, right);
}
public static void main(String[] args) {
// CEO
// / \
// VP1 VP2
// / \
// DIR1 DIR2
// /
// MGR1
DeskNode ceo = new DeskNode("CEO");
DeskNode vp1 = new DeskNode("VP1");
DeskNode vp2 = new DeskNode("VP2");
DeskNode dir1 = new DeskNode("DIR1");
DeskNode dir2 = new DeskNode("DIR2");
DeskNode mgr1 = new DeskNode("MGR1");
ceo.left = vp1; ceo.right = vp2;
vp1.left = dir1; vp2.right = dir2;
dir1.left = mgr1;
TreeDiameterNodes td = new TreeDiameterNodes();
System.out.println("Diameter (nodes): " + td.diameter(ceo));
}
}
Diameter (nodes): 6
What is the difference between node-counted and edge-counted diameter?
Node-counted: leftHeight + rightHeight + 1. Edge-counted: leftHeight + rightHeight. A single node has diameter 1 (nodes) or 0 (edges). Always state which convention you are using.
| Convention | Formula | Single node | Path A-B-C |
|---|---|---|---|
| Nodes | left + right + 1 | 1 | 3 |
| Edges | left + right | 0 | 2 |
// Nodes version
maxDiameter = Math.max(maxDiameter, left + right + 1);
// Edges version
maxDiameter = Math.max(maxDiameter, left + right);
Why is the naive approach quadratic?
The naive approach calls a separate height function at every node. On a skewed tree, height at the root is O(n), at its child O(n-1), totaling O(n^2). The fused approach computes each node's height once.
// NAIVE: O(n^2) on skewed trees
public int naiveDiameter(DeskNode root) {
if (root == null) return 0;
int through = heightSeparate(root.left) + heightSeparate(root.right) + 1;
return Math.max(through, Math.max(naiveDiameter(root.left), naiveDiameter(root.right)));
}
Why can the longest path skip the root?
The longest path connects two nodes through their lowest common ancestor, which may be any node in the tree. Evaluating the candidate at every node ensures paths not passing through the root are captured.
// A
// /
// B
// / \
// C D
// \
// E
// Longest: C → B → D → E = 4 nodes, goes through B not A
What are the edge cases?
Empty tree (diameter 0), single node (diameter 1), and a completely skewed tree.
package com.bank.service;
import com.bank.model.DeskNode;
public class DiameterNodesEdgeCases {
public static void main(String[] args) {
TreeDiameterNodes td = new TreeDiameterNodes();
System.out.println("Empty: " + td.diameter(null));
System.out.println("Single: " + td.diameter(new DeskNode("A")));
DeskNode skewed = new DeskNode("A");
skewed.left = new DeskNode("B");
skewed.left.left = new DeskNode("C");
System.out.println("Skewed: " + td.diameter(skewed));
}
}
Empty: 0
Single: 1
Skewed: 3
How is this related to the edge-counted version and maximum path sum?
All three problems share the same post-order pattern: return one value to the parent while updating a global with another. In diameter (nodes): return height, update left + right + 1. In diameter (edges): return height, update left + right. In maximum path sum: return upward gain, update bending path sum.
// Shared pattern
private int helper(Node node) {
if (node == null) return 0;
int left = helper(node.left);
int right = helper(node.right);
global = Math.max(global, COMBINE(left, right, node));
return PROPAGATE(left, right, node);
}
What should a senior engineer know?
A senior engineer states the counting convention explicitly and derives the O(n) solution by pointing to the repeated work in the naive approach. The fused post-order pattern is a reusable tool across multiple tree problems.
In production at National Bank of India, this analysis measures the longest escalation chain in the org hierarchy. An over-long chain slows approvals, so the diameter is reported as a health metric.
int chainLength = new TreeDiameterNodes().diameter(orgRoot);
if (chainLength > THRESHOLD) {
alertService.send("Escalation chain " + chainLength + " nodes exceeds limit.");
}
Visual Overview
Post-Order Diameter (Nodes)
CEO height=3
/ \ diameter through CEO: 3+2+1=6
VP1 VP2 height=2, height=2
/ \
DIR1 DIR2 height=1, height=1
/
MGR1 height=1
maxDiameter: 1 → 2 → 3 → 4 → 6
Answer: 6 nodes
Path: MGR1 → DIR1 → VP1 → CEO → VP2 → DIR2
Key Takeaway
The tree diameter counted in nodes is the longest path between any two nodes, measured by how many nodes it visits. The key insight is that the longest path through any node equals leftHeight + rightHeight + 1 (left depth, the node itself, right depth). A single post-order traversal returns each subtree's height while updating a shared maximum with this candidate, keeping the algorithm linear.
The naive approach recomputes heights at every node and degrades to quadratic on skewed trees. The fused approach computes each node's height exactly once. This pattern of returning one value while updating a global with another is reusable across diameter (edges), diameter (nodes), and maximum path sum problems.
Always state the counting convention. Node-counted diameter uses left + right + 1; edge-counted uses left + right. A single node has diameter 1 in nodes and 0 in edges. Confusing the two is the most common mistake.
In our banking system at National Bank of India, this measures the longest escalation chain in the org hierarchy. An over-long chain slows approvals, so the diameter is tracked as a health metric. The path often runs between two deep branches through a mid-level manager rather than through the CEO.
Remember one sentence: fuse height and diameter in post-order; leftHeight + rightHeight + 1 at each node is the candidate diameter in nodes.
---