On this page

Diameter of Binary Tree

Given the root of a binary tree, return the length of its diameter: the length of the longest path between any two nodes. The path may or may not pass through the root. The length is the number of edges on the path.

Constraints:

  • The number of nodes is in the range [1, 10^4].
  • -100 <= Node.val <= 100

Intuition

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

The longest path here is 4 to 2 to 1 to 3 to 6 with 4 edges (5 to 2 to 1 to 3 to 6 is the same length). Every path has a highest node where it turns. For that node, the longest path through it goes down the deepest left chain and the deepest right chain, so its length in edges is left height + right height, where each height is measured in nodes below this node.

So the diameter is the maximum of lh + rh over all nodes.

Brute Force

For every node, compute the height of its left and right subtree separately and take lh + rh. Keep the maximum. Recomputing heights for every node makes this O(n^2) on a skewed tree.

Optimal Approach: Update the Answer While Computing Height

Reuse the height function from the previous problem, and update a global diameter inside it.

  1. If the node is null, return 0.
  2. Compute lh and rh recursively.
  3. Update diameter = max(diameter, lh + rh). This is the longest path that turns at this node.
  4. Return 1 + max(lh, rh) as the height for the parent.

Height returned to the parent is a single downward chain, while the diameter candidate uses both sides. Keeping those two ideas apart is the core of this problem.

Code

class Solution {
int diameter = 0;
int height(TreeNode* node) {
if (node == nullptr) return 0;
int lh = height(node->left);
int rh = height(node->right);
diameter = max(diameter, lh + rh);
return 1 + max(lh, rh);
}
public:
int diameterOfBinaryTree(TreeNode* root) {
diameter = 0;
height(root);
return diameter;
}
};

Complexity

Time: O(n)

One pass computes the height and the diameter together. The brute force is O(n^2).

Space: O(h)

Recursion stack depth equals the tree height.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Every path has a highest node where it turns, and the longest path through a node is its left height plus its right height. So the diameter is the maximum of left height plus right height over all nodes. The brute force computes both heights at every node, which is O of n squared. Instead I compute height recursively and update a global diameter inside the same function. For each node I get the left and right heights, update the diameter with their sum, and return one plus the max of the two to the parent. The parent only gets a single chain, but the diameter uses both sides. That is one pass, so O of n time, and O of h space."
Next TopicBinary Tree Maximum Path Sum