Diameter of Binary Tree LeetCode 543

LeetCode 543 Diameter of Binary Tree asks you to find the diameter of a binary tree. The diameter is defined as the length of the longest path between any two nodes in the tree. The path length is measured in edges — not nodes — so a path visiting k nodes has length k-1. The diameter is the maximum number of edges on any root-to-leaf or leaf-to-leaf path in the tree.

The problem is straightforward to state but the naive approach has a subtle flaw: the longest path does not have to pass through the root. It can be entirely contained within a subtree. This means you cannot simply compute leftDepth + rightDepth at the root and return that value — you must examine every node as a potential turning point and take the global maximum.

The constraints are: the number of nodes is between 1 and 10,000, and node values are between -100 and 100. The tree is a standard binary tree with no guaranteed balance. The return value is the length in edges, so for a single-node tree the diameter is 0.

A common mistake is computing leftDepth + rightDepth at the root and returning that value. This only works if the longest path happens to pass through the root. In general, the diameter can be a leaf-to-leaf path that is entirely within a left or right subtree, never touching the root at all.

Consider a tree where the root has a right child, but the left subtree is a long chain of nodes going 10 levels deep. The longest path in this tree is entirely in the left subtree — it connects the leftmost leaf to the rightmost leaf of that left subtree. If you only compute the diameter at the root as leftDepth + rightDepth, you see leftDepth=10 and rightDepth=1, giving 11. But the actual diameter within the left subtree could be longer.

The correct approach is to treat every node as a potential "turning point" where the path bends — going down through the left subtree on one side and down through the right subtree on the other. The diameter at node v is leftHeight(v) + rightHeight(v). You compute this for every node and track the global maximum across all of them.

The efficient O(n) solution uses post-order DFS: visit the left subtree, visit the right subtree, then process the current node. At each node, you already have the heights of the left and right subtrees from the recursive calls. The diameter through this node is leftHeight + rightHeight. Update the global maximum with this value, then return the height of this node to its parent as 1 + max(leftHeight, rightHeight).

The height of a null node is -1 (or you can define it as 0 for leaf children — the convention that works cleanly here is: height of null = -1, height of leaf = 0, so that leftHeight + rightHeight for a leaf = -1 + -1 = -2 edges — which means you must offset). The cleaner convention used in most implementations: height of null = 0, height of leaf = 1. With this convention, leftHeight + rightHeight for a node where both children are leaves = 1 + 1 = 2 edges, which is correct — the path leaf-node-leaf has 2 edges.

Using height(null)=0 and height(leaf)=1: for any node, leftHeight = height(node.left), rightHeight = height(node.right). Diameter at this node = leftHeight + rightHeight (the path goes leftHeight edges down the left, and rightHeight edges down the right, meeting at this node). Height returned to parent = 1 + max(leftHeight, rightHeight). This single DFS pass visits every node exactly once, giving O(n) time and O(h) space for the call stack.

The DFS function computes two different things simultaneously. It returns the height of the current subtree so the parent node can use it to compute its own diameter. But it also updates a global diameter variable as a side effect. These are different values serving different purposes, and conflating them leads to bugs.

Height is a local property: the height of a node is the maximum number of edges from that node to any leaf in its subtree. It propagates upward through return values so each parent can learn how far down its children extend. Diameter is a global property: it is the maximum path length across the entire tree, and the path can involve any two nodes — it does not propagate upward in a simple way.

The reason we need a separate global diameter variable is that the diameter through a node is not the same as the height of the node. A node with leftHeight=3 and rightHeight=4 has a diameter of 7 through it, but a height of 5. If you tried to return max(leftHeight + rightHeight, 1 + max(leftHeight, rightHeight)) you would break the height computation that the parent depends on. The pattern — return one value, update another — is the key insight.

Consider the tree [1, 2, 3, 4, 5]: root is 1, left child is 2 with children 4 and 5, right child is 3 with no children. The post-order DFS visits 4, then 5, then 2, then 3, then 1. At node 4: left=0, right=0, diameter through 4 = 0, return height 1. At node 5: left=0, right=0, diameter through 5 = 0, return height 1. At node 2: leftHeight=1 (from 4), rightHeight=1 (from 5), diameter through 2 = 1+1 = 2, update global max to 2, return height 2.

At node 3: left=0 (null), right=0 (null), diameter through 3 = 0, return height 1. At root node 1: leftHeight=2 (from subtree rooted at 2), rightHeight=1 (from node 3), diameter through 1 = 2+1 = 3, update global max to 3, return height 3. The DFS completes with global diameter = 3, which is the correct answer: the longest path is 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3, both having 3 edges.

Notice that the diameter through root (3) is larger than the diameter through node 2 (2). This demonstrates that the longest path does pass through the root in this example, but in general you must check all nodes. If node 3 had no children and the subtree at node 2 were replaced by a longer chain, the root diameter would be smaller than the internal diameter, and only by tracking the global maximum across all nodes do you get the correct answer.

Python implementation uses a nonlocal variable for diameter inside a nested DFS function. Define diameter = 0 in the outer scope. The inner dfs(node) function uses nonlocal diameter, computes leftH = dfs(node.left) and rightH = dfs(node.right), updates diameter = max(diameter, leftH + rightH), and returns 1 + max(leftH, rightH). Call dfs(root) and return diameter. The complete solution is 8 lines. Time complexity O(n), space complexity O(h) for the call stack where h is the tree height.

Java implementation uses a class-level or instance-level int[] diameter = {0} (an array to allow mutation inside a lambda or nested method) or a class field. The helper method int dfs(TreeNode node) returns the height. Inside: if node == null return 0; int leftH = dfs(node.left); int rightH = dfs(node.right); diameter[0] = Math.max(diameter[0], leftH + rightH); return 1 + Math.max(leftH, rightH). Call dfs(root) in diameterOfBinaryTree and return diameter[0].

Both solutions share the same O(n) time and O(h) space profile. For a balanced tree, O(h) = O(log n). For a skewed tree (linked list shape), O(h) = O(n), which is the worst case for stack space. The iterative equivalent requires an explicit stack with a two-pass approach (first compute heights bottom-up, then compute diameters), which is more complex and rarely needed in practice since n is at most 10,000 and recursion depth is manageable.

Diameter of Binary Tree belongs to the post-order DFS family where you combine left and right subtree results at each node. The closest relative is Binary Tree Maximum Path Sum (LeetCode 124), which uses the same "return arm extension, update global max with two-arm sum" pattern. The difference is that path sum uses node values (which can be negative, requiring max(0, leftGain) to discard negative arms), while diameter uses heights (which are always non-negative).

Maximum Depth of Binary Tree (LeetCode 104) is the simplified version: the depth of a tree equals the height of the root, so you just return 1 + max(leftH, rightH) without tracking a global max. Lowest Common Ancestor (LeetCode 236) is another post-order DFS problem where you propagate found-node flags upward and determine the LCA at the first node where both flags are true. Symmetric Tree and Balanced Binary Tree also use the same post-order, combine-left-and-right pattern.

The diameter family extends to graphs: diameter of an undirected tree graph (two-BFS approach), diameter of a weighted tree, and longest increasing path in a matrix (LeetCode 329, which is diameter-like DFS on a DAG). Once you internalize the post-order pattern — compute left, compute right, combine, update global, return to parent — a wide range of seemingly different problems reduce to the same structural template.