Log inSign up
easyleetcodeNot Started

Diameter of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1 · Example 1: Path Through Root:

Input: root = [1, 2, 3, 4, 5]
Output: 3
Explanation: Longest path is [4, 2, 1, 3] or [5, 2, 1, 3], length 3 edges.

Example 2 · Example 2: Two Node Tree:

Input: root = [1, 2]
Output: 1
Explanation: Path is 1 -> 2 (1 edge).

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the bottom-up return-one-thing-update-another DFS technique.
  • Distinguish between path length (edges) and node count.
  • Understand why diameter does not necessarily pass through the tree root.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Longest path between any two nodes in a binary tree.
  • Path does not necessarily pass through root.
  • Maximum path sum / length in tree.

Algorithmic Decision Tree:

  • int height(node): if (!node) return 0;
  • lh = height(node.left), rh = height(node.right);
  • diameter = max(diameter, lh + rh);
  • return 1 + max(lh, rh);

Connected Patterns:

Binary Tree Maximum Path SumMaximum Depth of Binary TreeBalanced Binary Tree

1. Top-Down Height Calculation

Intuition

Define height(node). At each node, compute height(node.left) + height(node.right), and take the maximum across all nodes by recursing.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Define height(node) returning 1 + max(height(left), height(right)).
  2. Step 2: For each node, local diameter = height(left) + height(right).
  3. Step 3: Return max(local, diameter(left), diameter(right)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int height(TreeNode* node) {
10 if (!node) return 0;
11 return 1 + max(height(node->left), height(node->right));
12 }
13 int diameterOfBinaryTree(TreeNode* root) {
14 if (!root) return 0;
15 int cur = height(root->left) + height(root->right);
16 int l = diameterOfBinaryTree(root->left);
17 int r = diameterOfBinaryTree(root->right);
18 return max({cur, l, r});
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n^2) — Repeatedly computes heights for subtrees at every level, taking O(n2) worst case on skewed trees.
  • Space complexity: O(h) — Call stack takes O(h) space.

2. Top-Down with Height Memoization

Intuition

Compute heights once in postorder and store in a map. Then traverse nodes and compute lh + rh in O(1) per node.

When to apply: When caching heights explicitly.

Algorithm

  1. Step 1: Compute height for all nodes and cache in map.
  2. Step 2: Traverse tree and compute map[node.left] + map[node.right].
  3. Step 3: Track global maximum.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 unordered_map<TreeNode*, int> heights;
10 int calcH(TreeNode* node) {
11 if (!node) return 0;
12 return heights[node] = 1 + max(calcH(node->left), calcH(node->right));
13 }
14 int diameterOfBinaryTree(TreeNode* root) {
15 calcH(root);
16 int maxD = 0;
17 for (auto& [node, h] : heights) {
18 int lh = node->left ? heights[node->left] : 0;
19 int rh = node->right ? heights[node->right] : 0;
20 maxD = max(maxD, lh + rh);
21 }
22 return maxD;
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Two passes over the tree.
  • Space complexity: O(n) — Hashmap stores heights for all n nodes.

3. Single-Pass Bottom-Up Postorder DFS

Intuition

A helper dfs(node) returns the height of the subtree. At each node, compute lh = dfs(node.left) and rh = dfs(node.right). Update maxDiameter = max(maxDiameter, lh + rh). Return 1 + max(lh, rh).

When to apply: Standard optimal solution.

Algorithm

  1. Step 1: Initialize maxDiameter = 0.
  2. Step 2: Define dfs(node):
  3. - If node == null return 0.
  4. - lh = dfs(node.left), rh = dfs(node.right).
  5. - maxDiameter = max(maxDiameter, lh + rh).
  6. - Return 1 + max(lh, rh).
  7. Step 3: Call dfs(root).
  8. Step 4: Return maxDiameter.

Diameter Trace for root = [1, 2, 3, 4, 5]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Leaves 4 and 5 return height 1 to node 2
Visual state
Values and pointers at this exact step
tree
Root
1
Node 2
2 (h=2)
Node 3
3

Node order shown; add connections to display explicit tree edges.

curr: 2
Check / comparison
At node 2: lh=1, rh=1 -> local diam = 2
Decision / next transition
diameter = max(0, 2) = 2. Return height 2.
Why this step matters

Step 1: Leaves 4 and 5 return height 1 to node 2. At node 2: leftH=1, rightH=1. Local diameter = 1 + 1 = 2. Max diameter updated to 2. Node 2 returns height 1 + max(1, 1) = 2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int maxD = 0;
10 int dfs(TreeNode* node) {
11 if (!node) return 0;
12 int lh = dfs(node->left);
13 int rh = dfs(node->right);
14 maxD = max(maxD, lh + rh);
15 return 1 + max(lh, rh);
16 }
17 int diameterOfBinaryTree(TreeNode* root) {
18 maxD = 0;
19 dfs(root);
20 return maxD;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) — Visits every node exactly once in linear O(n) time.
  • Space complexity: O(h) — Call stack takes O(h) space.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Top-Down HeightO(n^2)O(h)Recompute height at every node.Repeated subtree traversals.
2.Height MemoizationO(n)O(n)Cache heights in map.Hashmap overhead.
3.Bottom-Up DFSOptimalO(n)O(h)Return height while updating global diameter.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: diameter is 0 (0 edges).
  • Two nodes (parent and child): diameter is 1.
  • Diameter completely within one subtree (does not cross root).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether diameter is measured in nodes or edges (LeetCode measures edges: lh + rh).
  2. Explain why the naive approach of calculating height(left) + height(right) at every node is O(n2), and how post-order bottom-up combines it into O(n).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Does the longest path (diameter) of a binary tree always pass through the root node?

Back to DSA Sheet