Problem overview
The method diameter receives the root of a binary tree, a TreeNode | null, and returns its diameter: the length of the longest path between any two nodes. The length counts edges, not nodes, and the path may or may not pass through the root.
In the first example, the tree built from [1,2,3,4,5] has root 1 with children 2 and 3, and node 2 has children 4 and 5. The path 4, 2, 1, 3 has three edges, so the answer is 3. In the second, [1,2] has a single edge, so the answer is 1.
Approach: combine the heights of the two sides
Look at the longest path through a given node. It goes down as far as possible on the left, comes up through the node, and goes down as far as possible on the right. Its length is the height of the left side plus the height of the right side, with heights counted in edges from the node.
The straightforward method calls a separate height function for every node and takes the best total, which repeats the same work over and over and can reach O(n²). A single post-order pass avoids it: each recursive call reports two numbers for its subtree, the height and the best diameter found inside it. The parent combines them in constant time.
At a node, with the children's reports in hand:
- the height of this node is the larger child height, plus one edge for the step down to that child;
- the diameter is the largest of three: the left subtree's best, the right subtree's best, and the path that bends at this node, which is the sum of the two heights.
The third candidate is what covers paths that go through the node. The first two cover paths that stay inside one subtree and so may avoid the root altogether.
Step by step
- Call the helper on the root and return element 1 of its result, the diameter. Element 0 is the height.
- Declare the helper. It takes a
TreeNode | nulland returns anumber[]of length two. - Base case. An empty subtree has height 0 and diameter 0, so return
[0, 0]. - Recurse left and destructure the result into
leftHeightandleftDiameter. Uselet, because the height is changed in a later step. - Recurse right and destructure it into
rightHeightandrightDiameterthe same way. - Add the edge to the left child. A child's height counts the edges below the child, so add 1 when the left child exists and 0 otherwise.
- Add the edge to the right child in the same way.
- Compute this node's height as the larger of the two side heights.
- Compute the diameter as the maximum of the left diameter, the right diameter and
leftHeight + rightHeight.Math.maxaccepts all three at once. - Return the height first and the diameter second, the order the caller reads them in.
The solution in TypeScript
class Solution {
dfs(root: TreeNode | null): number[] {
if (!root) {
return [0, 0];
}
let [leftHeight, leftDiameter] = this.dfs(root.left);
let [rightHeight, rightDiameter] = this.dfs(root.right);
leftHeight += root.left != null ? 1 : 0;
rightHeight += root.right != null ? 1 : 0;
let height = Math.max(leftHeight, rightHeight);
let diameter = Math.max(leftDiameter, rightDiameter, leftHeight + rightHeight);
return [height, diameter];
}
diameter(root: TreeNode | null): number {
return this.dfs(root)[1];
}
}
A leaf shows how the edge counting works: both children are missing, so both heights stay 0 and the leaf reports [0, 0]. For [1,2,3,4,5], node 2 gets height 0 from each leaf, adds 1 for each existing child and reports height 1 and diameter 2. Node 3 reports [0, 0]. At the root, the left height becomes 1 + 1 = 2 and the right height becomes 0 + 1 = 1, so the diameter is the maximum of 2, 0 and 2 + 1 = 3, which is 3, and the root reports [2, 3].
The TypeScript details worth a closer look:
- Array destructuring.
let [leftHeight, leftDiameter] = this.dfs(root.left)reads the first two elements of the returned array into two variables. TypeScript types both asnumber. It is only a convenient syntax: the function returns an ordinary array. letversusconst.leftHeightandrightHeightare updated with+=, so they needlet. The other variables are never reassigned and could beconst.- The conditional expression.
root.left != null ? 1 : 0evaluates to 1 or 0, and+=adds it. The loose comparison!= nullis also true forundefined, which can't occur here. Math.maxwith several arguments. It accepts any number of arguments, so no nesting is needed for three values.- Return type.
number[]doesn't say the array has two elements. A tuple type such as[number, number]would, but the lesson's choice works the same at run time.
Complexity
Let n be the number of nodes and h the height.
Time: O(n). Each node is visited once, and each visit does a constant amount of work with the two reports it receives.
Space: O(h). The only extra memory is the recursion, one call per level, plus a two-element array per call. It is O(log n) for a balanced tree and O(n) for a chain.
Edge cases and common mistakes
- A single node. The diameter is 0, because a path of one node has no edges.
- Counting nodes instead of edges. For
[1,2]the answer is 1, not 2. That is why the code adds 1 per existing child and not per node. - Forgetting the edge to the child. Without
+= 1for existing children, a tree of three nodes in a line would report 0 instead of 2. - Assuming the longest path goes through the root. In the tree
[1,2,null,3,4,5,null,null,6,7], the longest path is 7, 5, 3, 2, 4, 6 with five edges, while the longest path through the root has only four. Taking the maximum with the children's diameters is what handles this. - Adding a missing child's height. A missing child contributes no edge at all, which is the reason for the conditional.
- Returning the pair in the wrong order. The caller reads the height at index 0 and the diameter at index 1.
- Deep trees. Each level of a chain-shaped tree is one nested call, and the JavaScript call stack is limited. In a test with Node 22's default stack, a left-leaning chain of 4,000 nodes worked and one of 5,000 threw a
RangeError. The exact limit depends on the size of each call, so very unbalanced trees are the risk.
Testing
[1,2,3,4,5]gives3.[1,2]gives1.[1]gives0.[1,2,null,3,null,4], a left-leaning chain, gives3.[1,2,null,3,4,5,null,null,6,7]gives5, with a path that avoids the root.