# Diameter of Binary Tree

- **Canonical ID**: `diameter-of-binary-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/diameter-of-binary-tree
- **Difficulty**: easy
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/diameter-of-binary-tree/

## 1. Core Invariant / The Trick

In a single bottom-up DFS returning height, any node `u` can serve as the highest turning point of a path of edge length `leftH + rightH`. Maintain `best = max(best, leftH + rightH)` globally while returning `1 + max(leftH, rightH)` upward.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(H)`
- **Proof**: Avoids quadratic repeated height calls by computing both subtree heights and updating the best through-node path in one post-order traversal.

## 3. Minimal Idiomatic Code

### Python
```python
def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0
    def height(node: Optional[TreeNode]) -> int:
        nonlocal best
        if not node:
            return 0
        lh, rh = height(node.left), height(node.right)
        best = max(best, lh + rh)
        return 1 + max(lh, rh)
    height(root)
    return best
```

### TypeScript
```typescript
export function diameterOfBinaryTree(root: TreeNode | null): number {
  let best = 0;
  const height = (node: TreeNode | null): number => {
    if (!node) return 0;
    const lh = height(node.left);
    const rh = height(node.right);
    best = Math.max(best, lh + rh);
    return 1 + Math.max(lh, rh);
  };
  height(root);
  return best;
}
```

### C++
```cpp
int diameterOfBinaryTree(TreeNode* root) {
    int best = 0;
    auto dfs = [&](auto& self, TreeNode* n) -> int {
        if (!n) return 0;
        int l = self(self, n->left), r = self(self, n->right);
        best = max(best, l + r);
        return 1 + max(l, r);
    };
    dfs(dfs, root);
    return best;
}
```

### Java
```java
int best = 0;
int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    height(root);
    return best;
}
int height(TreeNode n) {
    if (n == null) return 0;
    int l = height(n.left), r = height(n.right);
    best = Math.max(best, l + r);
    return 1 + Math.max(l, r);
}
```

### Go
```go
func diameterOfBinaryTree(root *TreeNode) int {
    best := 0
    var dfs func(*TreeNode) int
    dfs = func(n *TreeNode) int {
        if n == nil { return 0 }
        l, r := dfs(n.Left), dfs(n.Right)
        if l+r > best { best = l + r }
        return 1 + max(l, r)
    }
    dfs(root)
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Counting nodes instead of edges (diameter is edge count, i.e., `leftH + rightH`).
- Assuming the longest path passes through the root.

### Follow-ups
- Tree Diameter in a general undirected N-ary graph: run two BFS passes from any node to farthest U, then U to V.