154. Diameter of Binary Tree
🔗 LeetCode Problem: 543. Diameter of Binary Tree
📊 Difficulty: Easy
🏷️ Topics: Binary Trees, DFS, Height, Global Max, Post-order
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:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
- The number of nodes in the tree is in the range [1, 10^4]
- -100 <= Node.val <= 100
🌳 Visual Understanding - What is Diameter?
Definition of Diameter:
Diameter = Longest path between ANY two nodes
Path length = Number of EDGES (not nodes!)
Tree:
1
/ \
2 3
/ \
4 5
Possible paths:
1. [4, 2, 1, 3] → 3 edges ✓ (longest!)
2. [5, 2, 1, 3] → 3 edges ✓ (also longest!)
3. [4, 2, 5] → 2 edges
4. [4, 2, 1] → 2 edges
5. [2, 1, 3] → 2 edges
Diameter = 3 edges
Visual Examples:
EXAMPLE 1: Path doesn't go through root
1
/ \
2 3
/ \
4 5
Longest path: 4 → 2 → 1 → 3
Edges: 3
Diameter: 3 ✓
EXAMPLE 2: Path goes through root
1
/
2
/
3
Longest path: 3 → 2 → 1
Edges: 2
Diameter: 2 ✓
EXAMPLE 3: Path doesn't involve root
1
/
2
/ \
3 4
/
5
Longest path: 5 → 3 → 2 → 4
Edges: 3
Diameter: 3 ✓ (doesn't touch root!)
Key Observations:
1. Diameter may or may not pass through root
- Could be anywhere in tree
- Must check ALL nodes
2. At any node, longest path through it:
- Goes through left child
- Through node itself
- Through right child
→ leftHeight + rightHeight
3. Number of edges vs nodes:
- Path with 4 nodes = 3 edges
- Height of subtree = max edges to leaf
Similar to Problem 147 (Max Path Sum)! 🎯
🧠 The AHA Moment - Return vs Track Pattern!
The Core Insight:
At each node, TWO different things:
1. TRACK (Global): Diameter through this node
leftHeight + rightHeight
→ Might be the answer!
→ Update global max
2. RETURN (Parent): Height from this node
1 + max(leftHeight, rightHeight)
→ Parent needs this to calculate its diameter!
Same pattern as Problem 147 (Max Path Sum)! 🔑
Visual Comparison with Max Path Sum:
PROBLEM 147 (Max Path Sum):
Track: node.val + leftGain + rightGain
Return: node.val + max(leftGain, rightGain)
PROBLEM 154 (Diameter):
Track: leftHeight + rightHeight
Return: 1 + max(leftHeight, rightHeight)
SAME PATTERN, different values! ✨
Why Different Values?
At node, calculate diameter:
Node
/ \
Left Right
(h=2) (h=1)
Diameter THROUGH node:
leftHeight + rightHeight = 2 + 1 = 3
But parent can only use ONE branch!
Parent
|
Node
/ \
Left Right
Parent's path can't use BOTH children of node!
Must return: 1 + max(2, 1) = 3
Return = extendable path
Track = complete path
🧠 Recursive Thinking - Building the Solution
Base Case:
When at null?
→ Height = 0 (no edges)
if (node == null) return 0;
Recursive Case:
For any node:
STEP 1: Get heights from children
leftHeight = height(node.left)
rightHeight = height(node.right)
STEP 2: Calculate diameter through this node
currentDiameter = leftHeight + rightHeight
STEP 3: Update global maximum
maxDiameter = max(maxDiameter, currentDiameter)
STEP 4: Return height for parent
return 1 + max(leftHeight, rightHeight)
What Each Node Does:
Each node:
1. Gets heights from children
2. Calculates diameter through itself
3. Updates global if larger
4. Returns height to parent
Returns height, tracks diameter! 🎯
🎯 Solution: DFS with Global Maximum
Implementation:
class Solution {
private int maxDiameter;
public int diameterOfBinaryTree(TreeNode root) {
// Initialize global max
maxDiameter = 0;
// Start DFS (returns height, updates maxDiameter)
height(root);
// Return the tracked maximum
return maxDiameter;
}
private int height(TreeNode node) {
// Base case: null node has height 0
// Height = number of edges to deepest leaf
if (node == null) {
return 0;
}
// STEP 1: Get heights from children
// Post-order: process children first!
int leftHeight = height(node.left);
int rightHeight = height(node.right);
// STEP 2: Calculate diameter through current node
// Diameter = path going through left, node, right
// = leftHeight + rightHeight (edges on both sides)
int currentDiameter = leftHeight + rightHeight;
// STEP 3: Update global maximum
// Track the largest diameter seen so far
maxDiameter = Math.max(maxDiameter, currentDiameter);
// STEP 4: Return height for parent
// Height = 1 (edge to parent) + max of children heights
// Parent can only extend ONE branch, not both!
return 1 + Math.max(leftHeight, rightHeight);
}
}
Why Global Variable?
Can't return diameter because:
- Return value = height (needed by parent)
- Diameter = different calculation
Two separate concerns:
1. What parent needs (height) → return
2. What answer needs (diameter) → global
Global variable elegantly solves this! ✨
🔍 Detailed Dry Run - Complete Visualization
Tree:
1
/ \
2 3
/ \
4 5
Complete Call Stack:
═══════════════════════════════════════════════════
CALL STACK - CALCULATING DIAMETER
═══════════════════════════════════════════════════
maxDiameter = 0 (initially)
Level 0: height(1)
│
├─ LEFT: height(2) ───────────────────────────────┐
│ │
│ Level 1: height(2) │
│ │ │
│ ├─ LEFT: height(4) ─────────────────────┐ │
│ │ │ │
│ │ Level 2: height(4) │ │
│ │ │ │ │
│ │ ├─ LEFT: height(null) → 0 │ │
│ │ ├─ RIGHT: height(null) → 0 │ │
│ │ │ │ │
│ │ ├─ leftHeight = 0 │ │
│ │ ├─ rightHeight = 0 │ │
│ │ │ │ │
│ │ ├─ currentDiameter = 0 + 0 = 0 │ │
│ │ ├─ maxDiameter = max(0, 0) = 0 │ │
│ │ │ │ │
│ │ └─ return 1 + max(0, 0) = 1 │ │
│ │ │ │
│ ├─ leftHeight = 1 │ │
│ │ │
│ ├─ RIGHT: height(5) ────────────────────┐ │
│ │ │ │
│ │ Level 2: height(5) │ │
│ │ │ │ │
│ │ ├─ LEFT: height(null) → 0 │ │
│ │ ├─ RIGHT: height(null) → 0 │ │
│ │ │ │ │
│ │ ├─ leftHeight = 0 │ │
│ │ ├─ rightHeight = 0 │ │
│ │ │ │ │
│ │ ├─ currentDiameter = 0 + 0 = 0 │ │
│ │ ├─ maxDiameter = max(0, 0) = 0 │ │
│ │ │ │ │
│ │ └─ return 1 + max(0, 0) = 1 │ │
│ │ │ │
│ ├─ rightHeight = 1 │ │
│ │ │
│ ├─ currentDiameter = 1 + 1 = 2 │
│ ├─ maxDiameter = max(0, 2) = 2 ← Updated! │
│ │ │
│ └─ return 1 + max(1, 1) = 2 │
│ │
├─ leftHeight = 2 │
│ │
├─ RIGHT: height(3) ──────────────────────────────┐
│ │
│ Level 1: height(3) │
│ │ │
│ ├─ LEFT: height(null) → 0 │
│ ├─ RIGHT: height(null) → 0 │
│ │ │
│ ├─ leftHeight = 0 │
│ ├─ rightHeight = 0 │
│ │ │
│ ├─ currentDiameter = 0 + 0 = 0 │
│ ├─ maxDiameter = max(2, 0) = 2 │
│ │ │
│ └─ return 1 + max(0, 0) = 1 │
│ │
├─ rightHeight = 1 │
│ │
├─ currentDiameter = 2 + 1 = 3 │
├─ maxDiameter = max(2, 3) = 3 ← Updated! │
│ │
└─ return 1 + max(2, 1) = 3 │
═══════════════════════════════════════════════════
FINAL: maxDiameter = 3
═══════════════════════════════════════════════════
Visual Path at Each Node:
Node 4:
Height: 1
Diameter through: 0 + 0 = 0
Path: just [4]
Node 5:
Height: 1
Diameter through: 0 + 0 = 0
Path: just [5]
Node 2:
Height: 2
Diameter through: 1 + 1 = 2
Path: [4, 2, 5] (2 edges) ✓
maxDiameter = 2
Node 3:
Height: 1
Diameter through: 0 + 0 = 0
Path: just [3]
Node 1:
Height: 3
Diameter through: 2 + 1 = 3
Path: [4, 2, 1, 3] (3 edges) ✓
maxDiameter = 3
Answer: 3 ✓
Return Values vs Tracked Values:
Node 4: returns 1, tracks 0
Node 5: returns 1, tracks 0
Node 2: returns 2, tracks 2
Node 3: returns 1, tracks 0
Node 1: returns 3, tracks 3
maxDiameter = 3 (answer!)
🔍 Another Example - Diameter Not Through Root
Tree:
1
/
2
/ \
3 4
/
5
Expected diameter: 3 (path: 5→3→2→4)
Execution:
Node 5:
Height: 1
Diameter: 0
Node 3:
Height: 2 (from 5)
Diameter: 1 + 0 = 1
Node 4:
Height: 1
Diameter: 0
Node 2:
leftHeight: 2 (from 3)
rightHeight: 1 (from 4)
Diameter: 2 + 1 = 3 ✓ (path: 5→3→2→4)
maxDiameter = 3
Return: 1 + max(2, 1) = 3
Node 1:
leftHeight: 3 (from 2)
rightHeight: 0
Diameter: 3 + 0 = 3
maxDiameter = max(3, 3) = 3
Answer: 3 ✓
📊 Complexity Analysis
Time Complexity: O(n)
Visit each node exactly once
O(1) work per node:
- Calculate diameter
- Update max
- Return height
Total: O(n)
Space Complexity: O(h)
Recursion stack: O(h)
Best case (balanced): O(log n)
Worst case (skewed): O(n)
Global variable: O(1)
Total: O(h)
⚠️ Common Mistakes
Mistake 1: Counting Nodes Instead of Edges
// ❌ WRONG - Returns number of nodes
private int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
// Diameter = nodes in path ✗
maxDiameter = Math.max(maxDiameter, left + right + 1);
return 1 + Math.max(left, right);
}
// Problem: Counts nodes, not edges!
// Path [4,2,1,3] has 4 nodes but 3 edges
// Should calculate: leftHeight + rightHeight (no +1!)
// ✓ CORRECT - Count edges
maxDiameter = Math.max(maxDiameter, left + right); ✓
Mistake 2: Returning Diameter Instead of Height
// ❌ WRONG - Returns diameter
private int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
int diameter = left + right;
maxDiameter = Math.max(maxDiameter, diameter);
return diameter; // WRONG! Parent needs height!
}
// Problem: Returns diameter, not height!
// Parent can't calculate correctly
// ✓ CORRECT - Return height
return 1 + Math.max(left, right); ✓
Mistake 3: Not Using Global Variable
// ❌ WRONG - Trying to return diameter directly
public int diameterOfBinaryTree(TreeNode root) {
return helper(root); // Can't work!
}
private int helper(TreeNode node) {
if (node == null) return 0;
int left = helper(node.left);
int right = helper(node.right);
// What to return? Diameter or height?
// Can't return both! ✗
}
// ✓ CORRECT - Use global for diameter, return height
private int maxDiameter;
private int height(TreeNode node) {
// ... calculate and track diameter
return 1 + Math.max(left, right); // Return height
}
Mistake 4: Wrong Base Case
// ❌ WRONG - Leaf returns 1
if (node == null) return 0;
if (node.left == null && node.right == null) {
return 1; // WRONG!
}
// Problem: Height is edges, not nodes!
// Leaf has height 1 to parent, but 0 to itself
// ✓ CORRECT - Just handle null
if (node == null) return 0; ✓
// Let recursion handle rest naturally
Mistake 5: Not Understanding Height Definition
// Common confusion: What is height?
// Height = maximum number of EDGES from node to leaf
// Examples:
// Leaf node: height = 1 (1 edge to parent)
// null: height = 0 (no edges)
//
// Tree: 1
// /
// 2
//
// Node 2: height = 1 (leaf, 1 edge up)
// Node 1: height = 2 (1 + height(2))
// Formula: 1 + max(leftHeight, rightHeight)
// The +1 is the edge to current node! ✓
🎯 Pattern Recognition - Return vs Track Problems
Core Pattern: Global Max with Different Return
Template for return-vs-track problems:
private int globalMax;
public int solve(TreeNode root) {
globalMax = initialValue;
helper(root);
return globalMax;
}
private int helper(TreeNode node) {
if (node == null) return baseValue;
int left = helper(node.left);
int right = helper(node.right);
// TRACK: Complete structure at node
int complete = calculate(node, left, right);
globalMax = update(globalMax, complete);
// RETURN: Extendable path for parent
return extendable(node, left, right);
}
Related Problems:
1. Binary Tree Maximum Path Sum (Problem 147)
Track: node.val + leftGain + rightGain
Return: node.val + max(leftGain, rightGain)
SAME PATTERN!
2. Diameter of Binary Tree (Problem 154)
Track: leftHeight + rightHeight
Return: 1 + max(leftHeight, rightHeight)
SAME PATTERN!
3. Longest Univalue Path
Track: leftLen + rightLen (if same value)
Return: max(leftLen, rightLen) + 1
SAME PATTERN!
4. Binary Tree Cameras
Track: Total cameras needed
Return: State (covered/has camera/needs)
Similar structure!
When to Use This Pattern:
✓ Answer different from recursion return
✓ Need complete structure at node
✓ Complete structure not extendable to parent
✓ Track global max/min/count
✓ Return value for parent's calculation
🆚 Direct Comparison: Diameter vs Max Path Sum
Side-by-Side:
// DIAMETER OF BINARY TREE
private int maxDiameter;
public int diameterOfBinaryTree(TreeNode root) {
maxDiameter = 0;
height(root);
return maxDiameter;
}
private int height(TreeNode node) {
if (node == null) return 0;
int left = height(node.left);
int right = height(node.right);
// Track: Complete path
maxDiameter = Math.max(maxDiameter, left + right);
// Return: Extendable path
return 1 + Math.max(left, right);
}
// MAXIMUM PATH SUM (Problem 147)
private int maxSum;
public int maxPathSum(TreeNode root) {
maxSum = Integer.MIN_VALUE;
maxGain(root);
return maxSum;
}
private int maxGain(TreeNode node) {
if (node == null) return 0;
int leftGain = Math.max(0, maxGain(node.left));
int rightGain = Math.max(0, maxGain(node.right));
// Track: Complete path
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
// Return: Extendable path
return node.val + Math.max(leftGain, rightGain);
}
IDENTICAL STRUCTURE! ✨
Differences:
DIAMETER:
- Count edges
- Always positive
- Base: 0
- No need for max(0, child)
MAX PATH SUM:
- Sum values
- Can be negative
- Base: Integer.MIN_VALUE
- Need max(0, child) to ignore negatives
Structure same, details different! 🎯
📝 Quick Revision Notes
🎯 Core Concept
Find longest path (in edges) between any two nodes. May or may not pass through root. Use return vs track pattern: at each node, TRACK diameter through it (leftHeight + rightHeight), RETURN height to parent (1 + max(leftHeight, rightHeight)). Use global variable for tracking max. Height = edges to deepest leaf. Post-order: process children first.
⚡ Quick Implementation
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
public static TreeNode buildTree(Integer[] arr) {
if (arr == null || arr.length == 0 || arr[0] == null) {
return null;
}
TreeNode root = new TreeNode(arr[0]);
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int i = 1;
while (!queue.isEmpty() && i < arr.length) {
TreeNode current = queue.poll();
// Process left child
if (i < arr.length) {
if (arr[i] != null) {
current.left = new TreeNode(arr[i]);
queue.offer(current.left);
}
i++;
}
// Process right child
if (i < arr.length) {
if (arr[i] != null) {
current.right = new TreeNode(arr[i]);
queue.offer(current.right);
}
i++;
}
}
return root;
}
public static void print(TreeNode root) {
if (root == null) {
System.out.println("[]");
return;
}
List<String> result = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node != null) {
result.add(String.valueOf(node.val));
queue.offer(node.left);
queue.offer(node.right);
} else {
result.add("null");
}
}
while (!result.isEmpty() && result.get(result.size() - 1).equals("null")) {
result.remove(result.size() - 1);
}
System.out.println(result);
}
}
class Solution {
int diameter;
public int diameterOfBinaryTree(TreeNode root) {
// Approach - same as Problem 147 (Max Path Sum)
diameter = 0;
diameterOfBinaryTreeUtil(root);
return diameter - 1; // as diameter is number of edges
}
private int diameterOfBinaryTreeUtil(TreeNode root) {
if(root == null) {
return 0;
}
// Height of LST
int left = diameterOfBinaryTreeUtil(root.left);
// Height of RST
int right = diameterOfBinaryTreeUtil(root.right);
// THROUGH usecase (will go via ROOT or have root as final and will not extend)
diameter = Math.max(diameter, 1 + left + right);
// EXTEND usecase
return 1 + Math.max(left, right);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.diameterOfBinaryTree(TreeNode.buildTree(new Integer[] {1,2,3,4,5}))); // 3
System.out.println(s.diameterOfBinaryTree(TreeNode.buildTree(new Integer[] {1,2}))); // 1
}
}
🔑 Key Insights
Return vs Track:
At each node, TWO calculations:
TRACK (Complete path through node):
leftHeight + rightHeight
→ This might be the answer!
→ Update global maxDiameter
RETURN (Extendable path for parent):
1 + max(leftHeight, rightHeight)
→ Parent can only extend ONE branch!
Same as Problem 147 (Max Path Sum)! 🔑
Why Can't Return Both:
Parent needs height to calculate:
Parent
|
Node
/ \
Left Right
Parent's diameter:
Need Node's height (how far down can we go)
NOT Node's diameter (that's already complete)
If we return diameter:
Parent can't calculate its own diameter! ✗
Must return height, track diameter separately! ✓
Edges vs Nodes:
Path: [4, 2, 1, 3]
Nodes: 4
Edges: 3 ✓ (count gaps between nodes)
Height calculation:
null: 0 edges
Leaf: 1 edge (to parent)
Internal: 1 + max(left, right)
Diameter calculation:
leftHeight + rightHeight
(Edges from left + edges from right)
No +1 when calculating diameter! 🎯
Global Variable Necessity:
Can't return diameter because:
- Parent needs height for calculation
- Return value already used
Must track separately:
- Global variable for max diameter
- Return height for parent
Two pieces of info, one return value! ✨
🎪 Memory Aid
"Track COMPLETE (left + right)!"
"Return EXTENDABLE (1 + max)!"
"Count EDGES not nodes!"
"Global for max, return for height!" ✨
⚠️ Don't Forget
- Count edges not nodes (no +1 in diameter!)
- Return height to parent (not diameter!)
- Track in global variable (separate from return!)
- Post-order traversal (children first!)
- Height = 1 + max(left, right) (the +1 is the edge!)
- Same pattern as Max Path Sum (Problem 147!)
🎉 Congratulations!
You've mastered the return vs track pattern completely!
What You Learned:
✅ Diameter concept - Longest path in edges
✅ Return vs track - Two different values
✅ Global variable - When needed
✅ Height calculation - For parent's use
✅ Post-order pattern - Process children first
✅ Pattern recognition - Same as Problem 147!
The Pattern:
This pattern appears when:
- Answer ≠ return value
- Complete structure not extendable
- Need global max/min
- Return used for parent's calculation
Problems using it:
✓ Diameter of Binary Tree (154)
✓ Maximum Path Sum (147)
✓ Longest Univalue Path
✓ Binary Tree Cameras
Master once → Solve many! 🎯
Interview Mastery:
Interviewer: "Find diameter of binary tree"
Your response:
"This uses the return-vs-track pattern.
At each node:
- Track diameter through it: left + right
- Return height to parent: 1 + max(left, right)
Use global variable for max diameter
because return value is height (needed by parent).
Same pattern as Maximum Path Sum problem!
Time: O(n), Space: O(h)"
Shows pattern mastery! 💯
You've now mastered one of the most important patterns in tree algorithms! 🏆✨🎯