## Problem Statement

### Description

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.

### Examples

#### 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`

## Key Insights

In this problem we are asked to find the **length** of the longest path between two nodes in a **binary tree**. Since we can only traverse a **binary tree** from top to bottom, we know that the answer to this problem will include some sort of tree traversal.

If we draw out an example tree, we can see that the longest possible path in a **binary tree** will start at one **leaf node**, pass through a **lowest common ancestor**, and then terminate at another **leaf node**. In the diagram below, we can see that the longest path in the **binary tree** passes through node `2`

. If we know the max height of the `left`

and `right`

subtrees, we can calculate the maximum path length.

Since we need to know the max height of the `left`

and `right`

subtrees for each node we visit, we will need to use a **post-order traversal** to solve this problem. We can base our solution on Leetcode 104: Maximum Depth of Binary Tree. Only in our case, we will add some logic to compare the longest path at each node to the global max path.

## Python Solution

```
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
"""
T: O(N)
S: O(N) ~ worst; O(log N) ~ perfectly balanced
This solution is based on:
https://jessechaulk.com/posts/104-maximum-depth-of-binary-tree/
"""
self.ans = 0
def helper(node):
if not node:
return 0
# Find the max height of the left and right subtrees
left = helper(node.left)
right = helper(node.right)
# Check the sum of the left + right subtrees and update the
# longest path variable if applicable.
self.ans = max(self.ans, left + right)
# Return the height of the max of the left and right subtrees.
# Add 1 to the result to account for the height of the current
# node
return max(left, right) + 1
helper(root)
return self.ans
```