> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/trees/binary]
> [project group:: neetcode 150]
> [difficulty:: easy]
> [status:: done]
> [link:: https://leetcode.com/problems/diameter-of-binary-tree/]
> [up:: [[Leetcode MOC]]]
## Problem
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, 104]`.
- `-100 <= Node.val <= 100`
## Solution
### Mine
#### Python
#### Rust
### Neetcode
```python
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
res = [0]
def dfs(root):
if not root:
return -1
left = dfs(root.left)
right = dfs(root.right)
res[0] = max(res[0], 2 + left + right)
return 1 + max(left, right) # height
dfs(root)
return res[0]
```
## Things I Learned
### Neetcode Explanation
From each node, find the greatest depth of each child, add them together.
![[Pasted image 20230117211223.png]]
But we want longest:
![[Pasted image 20230117211300.png]]
Recurse, start from bottom, find diameter of those nodes. Bruteforce is $O(n^2)$.
For each node, we want diameter and height. Height is 1 + max(left, right) (see [[104. Maximum Depth of Binary Tree]])
Diameter = height(L) + height(R) + 2 from any node. a null child should be marked -1.
![[Pasted image 20230117211801.png]]
## Scratchpad
It seems like you just need to get the two greatest depths, then figure out the path between them. No idea how to do that.