Diameter of Binary Tree

Signal

"Longest path between any two nodes" sounds like it needs checking every pair, but it decomposes into a height computation with a side channel: the longest path through any given node is exactly left_height + right_height at that node — compute it once, during the same recursion that already computes height.

Approach

Run the normal height recursion. At each node, after getting the heights of both children, update a running best with left_height + right_height, then return 1 + max(left_height, right_height) upward as usual. The running best needs to survive across recursive calls — a closure variable via nonlocal works cleanly.

Skeleton

best = 0
def height(node):
    nonlocal best
    if not node: return 0
    l, r = height(node.left), height(node.right)
    best = max(best, l + r)
    return 1 + max(l, r)
height(root)
return best

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def diameter_of_binary_tree(root: TreeNode | None) -> int:
    best = 0

    def height(node: TreeNode | None) -> int:
        nonlocal best
        if node is None:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)
        return 1 + max(left, right)

    height(root)
    return best

Complexity

O(n) time — one pass, heights reused rather than recomputed. O(h) recursion stack space.

Pitfalls

• Diameter is measured in edges; left_height + right_height (both counted in nodes-below) already equals that edge count directly — don't add an extra 1.
• Calling height() separately for each node to check "is this the diameter" (instead of folding the check into one traversal) degrades to O(n²) on a skewed tree.