Given the root of a binary tree, return the length, in edges, of the longest path between any two nodes. That path doesn't need to pass through the root.
Example
Input root = [1,2,3,4,5]
Output 3
Key Pointers
The diameter through any node equals its left height plus its right height — the global answer is the max of that over every node, not just the root.
Compute it in a single pass by having a height helper update an outer "best" value as a side effect while it recurses.
Height and diameter are different quantities: height is 1 + max(child heights); diameter is the sum of both child heights.
Step-by-Step Analysis
Keep a variable diameter = 0 outside the recursion.
Define a height(node) helper; base case None returns 0.
Recursively get the left height and right height of the node's children.
Update diameter = max(diameter, left + right).
Return 1 + max(left, right) as this node's own height, and call height(root) once at the end to return diameter.
Complexity
Time: O(n) — Space: O(h)
Code
def diameterOfBinaryTree(root: TreeNode | None) -> int:
diameter = 0
def height(node: TreeNode | None) -> int:
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
Code Explanation
How the solution above works, piece by piece.
height(node) returns the number of nodes on the longest downward path from node (0 for an empty child).
For each node, left + right is the number of edges in the longest path that bends at that node.
diameter keeps the best of those over all nodes; nonlocal lets the inner function update it.
Return 1 + max(left, right) to the parent: a path can only continue upward through one side.
One pass: O(n) time, O(height) stack.
Visual Walkthrough
Running it on root = [1, 2, 3, 4, 5]:
The longest path through a node uses its left height plus its right height (in edges). Checking that at every node finds the best path even if it doesn't pass through the root; here it does: 4 → 2 → 1 → 3.