TreeEasyO(n) time · O(h) space

Diameter of Binary Tree

Mahabharata — The Widest Span — The Longest Path Through Any Node

व्यास — सबसे लम्बा पथ। हर नोड पर — बाएं + दाएं = उस नोड का व्यास॥

*Diameter — the longest path. At each node — left height + right height = diameter through that node.*

The Story

Find the diameter of a binary tree (length of the longest path between any two nodes; path need not pass through root).

For `[1,2,3,4,5]`: diameter=3 (path 4→2→1→3 or 5→2→1→3, length 3 edges). For `[1,2]`: diameter=1.

**Key insight:** The diameter through any given node = height(left subtree) + height(right subtree). Track the maximum diameter across all nodes.

```java int maxDiam = 0; public int diameterOfBinaryTree(TreeNode root) { height(root); return maxDiam; } int height(TreeNode root) { if (root == null) return 0; int left = height(root.left); int right = height(root.right); maxDiam = Math.max(maxDiam, left + right); // Diameter through this node return 1 + Math.max(left, right); // Height of this node } ```

Trace `[1,2,3,4,5]`: - height(4)=1. At 4: max=max(0,0+0)=0 - height(5)=1. At 5: max=max(0,0+0)=0 - height(2): left=1,right=1. max=max(0,1+1)=2. return 2 - height(3)=1. At 3: max stays 2 - height(1): left=2,right=1. max=max(2,2+1)=3. return 3 - Diameter=3 ✓ (edges, not nodes)

The Recompute-Height-at-Every-Node Approach

For each node: compute height(left)+height(right) separately. O(n²) due to repeated height computations.

java

int maxDiamBrute = 0;
public int diameterBrute(TreeNode root) {
    if (root == null) return 0;
    int lh = heightBrute(root.left), rh = heightBrute(root.right);
    maxDiamBrute = Math.max(maxDiamBrute, lh + rh);
    diameterBrute(root.left); diameterBrute(root.right);
    return maxDiamBrute;
}

The Single-Pass Height+MaxDiam Wisdom

height() returns height AND updates maxDiam = max(maxDiam, left+right) at each node. Single O(n) post-order pass.

java

int maxDiam = 0;

public int diameterOfBinaryTree(TreeNode root) {
    height(root);
    return maxDiam;
}

int height(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left);
    int right = height(root.right);
    maxDiam = Math.max(maxDiam, left + right);
    return 1 + Math.max(left, right);
}

Step-by-Step Walkthrough

Tree=[1,2,3]: height(2)=1,height(3)=1. At 1: maxDiam=2. Return 2 ✅

Deep Insight

**Diameter ≠ root's path:** The longest path may not go through the root. For example: ``` 1 / 2 / \ 3 4 ``` Diameter = 3 (path 3→2→4, going through node 2 not root 1).

The single-pass approach checks EVERY node as a potential 'highest point' of the diameter path, tracking the maximum.

**Edges vs Nodes:** LeetCode's diameter is in edges (left + right), not nodes (left + right + 1). Verify the problem statement.

**Generalization — Longest path in a tree (general graph):** Two BFS/DFS from any node then from farthest node. For binary trees, the single-pass post-order is more efficient.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n²)	O(h)	Height computed at each of n nodes
Optimal	O(n)	O(h)	Single post-order pass

Pattern Recognition

✅ Diameter: update global max at each node (left+right heights)
✅ Return height (not diameter) from the recursive function
✅ Single post-order pass; height function does double duty
✅ Path doesn't need to pass through root

**LeetCode Trigger Phrases:**
→ "diameter of binary tree"
→ Longest path between two nodes
→ Post-order with global variable update

Bhagavad Gita 18.78

यत्र योगेश्वरः कृष्णो यत्र पार्थो धनुर्धरः। तत्र श्रीर्विजयो भूतिर्ध्रुवा नीतिर्मतिर्मम॥

Wherever there is Krishna, the lord of yoga, and wherever there is Arjuna, the wielder of the bow, there will always be fortune, victory, prosperity, and sound morality.

Connection: The diameter of a binary tree is the longest span connecting two extreme points through the tree. Like the bridge between Krishna's wisdom and Arjuna's action — a span connecting the divine source to the executing hand — the diameter represents the greatest reach of the tree structure. At every node, the combined heights of both subtrees define the span possible there; the greatest such span across all nodes is the tree's true diameter.