Problem overview
The method Diameter receives the root of a binary tree and returns the length of its diameter: the longest path between any two nodes, counted in edges. The path may or may not pass through the root.
For [1, 2, 3, 4, 5], the node 1 has children 2 and 3, and 2 has children 4 and 5. The longest path is 4, 2, 1, 3 (or 5, 2, 1, 3). It has four nodes and three edges, so the answer is 3. For [1, 2] the only path is 1 to 2, which is one edge, so the answer is 1. A single node has diameter 0.
Approach: every longest path has a highest node
Every path in a tree goes up from one node to a highest point and then down to another node. At that highest node, the path is made of a downward chain into the left subtree and a downward chain into the right subtree. So the longest path whose highest node is x has length height(left) + height(right), where each height counts the edges from x, including the edge to the child.
The diameter is the best such value over all nodes. A direct translation computes the height of both subtrees at every node, which re-walks the same nodes many times and is O(n²) in the worst case, for example on a chain. The lesson avoids that by making each recursive call report two numbers for its subtree: its height and its diameter. The parent combines the two reports in constant time, so the tree is walked once.
For a node, with the edges to existing children already added to the child heights:
- the height is the larger of the two child heights;
- the diameter is the largest of the left diameter, the right diameter, and the path through this node,
leftHeight + rightHeight.
Step by step
- Delegate. Call
Dfs(root)and return element 1 of the array it returns. Element 0 is the height and element 1 is the diameter. - Declare the helper above
Diameteraspublic int[] Dfs(TreeNode root). A two-element array is a simple way to return two numbers. - Empty subtree. If
rootisnull, returnnew int[]{0, 0}: no height and no diameter. This ends the recursion below the leaves. - Left report. Recurse on
root.leftand unpack the array intoleftHeightandleftDiameter. - Right report. Do the same for
root.right. - Add the left edge. A child's height counts the edges below the child. If the left child exists, the edge from
rootto it adds 1. Without this, a node with one leaf child would have height 0 instead of 1. - Add the right edge in the same way. If there is no right child, nothing is added.
- Compute the height as the maximum of the two adjusted heights.
- Compute the diameter as the maximum of
leftDiameter,rightDiameterandleftHeight + rightHeight.Math.Maxtakes two arguments, so two calls are nested. - Return both as
new int[]{height, Diameter}, in the order the caller expects.
The solution in C#
class Solution {
public int[] Dfs(TreeNode root) {
if (root == null) {
return new int[]{0, 0};
}
int[] left = Dfs(root.left);
int leftHeight = left[0], leftDiameter = left[1];
int[] right = Dfs(root.right);
int rightHeight = right[0], rightDiameter = right[1];
leftHeight += root.left != null ? 1 : 0;
rightHeight += root.right != null ? 1 : 0;
int height = Math.Max(leftHeight, rightHeight);
int Diameter = Math.Max(Math.Max(leftDiameter, rightDiameter), leftHeight + rightHeight);
return new int[]{height, Diameter};
}
public int Diameter(TreeNode root) {
return Dfs(root)[1];
}
}
The C# details worth a look:
- Returning two values. The lesson uses an
int[]and indexes it by position. C# also has tuples such as(int, int), but the array keeps the code simple. The cost is that you must remember that index 0 is the height and index 1 is the diameter. - Multiple declarations.
int leftHeight = left[0], leftDiameter = left[1];declares two variables of the same type in one statement. - No implicit bool to int. C# doesn't convert a
boolto a number, soleftHeight += root.left != nullwould not compile. The conditional operator,root.left != null ? 1 : 0, turns the check into 1 or 0. - A local named like a method. The local variable
Diametershares its name with the public methodDiameter. This compiles, because the local lives only insideDfs. A name likediameterwould be easier to read. Math.Maxtakes exactly two arguments forint, hence the nesting.
Complexity
Time: O(n). Each node is visited once, and each visit does a constant number of operations, including allocating one small array.
Space: O(h), where h is the height of the tree, for the recursion. A balanced tree needs about log n frames and a chain needs n. Each call also creates a two-element array, but only the arrays of the calls on the current path are alive at the same time.
Edge cases and common mistakes
- Counting nodes instead of edges. The answer for
[1, 2]is 1, not 2. That is the reason the heights add the edge to an existing child instead of counting nodes. - Single node. Both children report 0, no edges are added, and the diameter is 0.
- Assuming the path goes through the root. A deep subtree can hold the longest path. Taking the maximum with
leftDiameterandrightDiameterhandles that. In a tree whose root has one long, bushy child, the answer lives entirely inside that child. - Adding the edge for a missing child. The base case also returns height 0 for
null, so adding 1 unconditionally would make a missing child count as an edge. The conditional adds the edge only when the child exists. - Chain-shaped trees. A chain of
knodes has diameterk - 1, and the recursion goes as deep as the chain.
Testing
[1, 2, 3, 4, 5]gives 3.[1, 2]gives 1.[1]gives 0.- The tree
[1, 2, 3](root with two leaf children) gives 2.