An on-call product stores an escalation tree: each queue forks into at most two child queues. The SLO for a cross-team page is the hop count between any two on-calls — the worst handoff chain if two incidents need the same people talking. The intern version, at every queue, walked the left fork for height, walked the right fork for height, added them, then did the same work in both children. A dozen queues painted instantly. A million-node imported org chart still re-walked the same leaves from every ancestor.

The longest path through a node is leftHeight + rightHeight, counted in edges. Maximum Depth is nodes on a root-to-leaf walk. Diameter is the longest path between any two nodes, and this prompt counts edges. A binary tree already gives left and right. DFS owns recursion versus an explicit stack. Here we only care about returning height and tracking a global max of leftHeight + rightHeight. Do not stamp finish times or hunt back edges.

The problem

Given the root of a binary tree, return its diameter — the number of edges on the longest path between any two nodes. The path does not have to pass through the root. An empty tree is 0. A single node is 0.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees, counting edges not nodes:

      1
     / \
    2   3
   / \
  4   5     →  3

      1
     /
    2       →  1
[]          →  0
[1]         →  0

Note: Some definitions count nodes on that path, which would make a lone node 1. This prompt counts edges. Do not return 1 for a lone node and do not return height(root) as the diameter.

Height from scratch at every node is the honest brute force

At each node, compute height of the left subtree and of the right, add them as the path through this node, then take the max with the same work in both children. Correct. Extra: every ancestor re-walks the same descendants. Collecting every pair of leaves is the same answer with more furniture — the longest path through a node is already the deepest leaf on each side.

The Java is that nested walk:

int diameterCollect(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int through = height(root.left) + height(root.right);
    return Math.max(through,
            Math.max(diameterCollect(root.left), diameterCollect(root.right)));
}

int height(TreeNode node) {
    if (node == null) {
        return 0;
    }
    return 1 + Math.max(height(node.left), height(node.right));
}

At a dozen nodes this is a rounding error. At a million-node spine you still walk overlapping subtrees from every ancestor. The intended answer never asks height twice: one DFS returns height and updates a running max of left + right.

One DFS, height out, diameter on the side

Null returns 0. A node asks both children for height, offers left + right to the global max, and returns 1 + max(left, right). Height of a leaf is 1 (both children null). left + right is edges through this node because each returned height is a node count, matching Maximum Depth.

height(4) = 1     height(5) = 1     height(3) = 1
height(2) = 1 + max(1, 1) = 2,  through = 1 + 1 = 2
height(1) = 1 + max(2, 1) = 3,  through = 2 + 1 = 3
best = 3

The Java is that recurrence with a one-slot box for the max:

int diameterOfBinaryTree(TreeNode root) {
    int[] best = {0};
    height(root, best);
    return best[0];
}

int height(TreeNode node, int[] best) {
    if (node == null) {
        return 0;
    }
    int left = height(node.left, best);
    int right = height(node.right, best);
    best[0] = Math.max(best[0], left + right);
    return 1 + Math.max(left, right);
}

Time is O(n) — each node is visited once. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; the iterative version with an explicit stack is the same bound without blowing the JVM stack.

What interviewers usually poke next

  • Edges vs nodes. Maximum Depth counts nodes; this counts edges. A leaf is depth 1 and diameter 0. Name the unit before you edit the + 1.
  • Not necessarily through the root. height(left) + height(right) at the root is one candidate, not the answer. The running max exists because a child’s through-path can beat the root’s.
  • Binary Tree Maximum Path Sum. Same post-order shape; it sums values and a node may start a new path. Do not add node.val in diameterOfBinaryTree. Optional URL: /interview/trees/hard/binary-tree-maximum-path-sum/.
  • Million-node spine. Recursion depth is O(h). Say you would switch to an explicit stack so the JVM does not blow the stack.

You are done with this problem when you can say empty is 0, a lone node is 0, and a height DFS plus a running max of left + right is the whole algorithm — not nested height walks from every ancestor.