Diameter of Binary Tree

The problem

The diameter of a binary tree is the length (in edges) of the longest path between any two nodes. The path need not pass through the root, and the two endpoints can be any two nodes.

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

Pattern: tree DP with "return one, track another"

Same shape of recursion as Maximum Depth, but you need two pieces of information at each node:

• Return value: the depth from this node — going up uses only one child.
• Tracked globally: the diameter passing through this node — uses both children, since the path can bend at this node.

This is the canonical tree-DP idiom: the recursion returns the quantity the parent needs, while a global tracker captures the "answer through this node" quantity. Sibling problems include Binary Tree Max Path Sum, Longest Univalue Path, and the diameter variant on N-ary trees.

Solution

def diameter(root: Node | None) -> int:
    """O(n).  Return depth from each subtree; track diameter globally."""
    best = 0
    def depth(node):
        nonlocal best
        if node is None:
            return 0
        l = depth(node.left)
        r = depth(node.right)
        best = max(best, l + r)        # candidate diameter passing through this node
        return 1 + max(l, r)            # depth returned to parent
    depth(root)
    return best

Why the naive version is O(n²)

The natural-first-attempt version computes depth independently at every node, recursing into both children to measure them again, then recurses to gather diameters. Each depth call is O(subtree size); summed over all nodes that's O(n²). The fix is to fold both quantities into a single post-order traversal so each node is visited once.

def diameter_naive(root):
    """For each node, compute the through-diameter and recurse. O(n^2) worst case
    because depth() is called repeatedly."""
    if root is None: return 0
    def depth(node):
        if node is None: return 0
        return 1 + max(depth(node.left), depth(node.right))
    through = depth(root.left) + depth(root.right)
    return max(through, diameter_naive(root.left), diameter_naive(root.right))

Trace

Tree:        1
            / \
           2   3
          / \
         4   5
        /
       6

depth(6): l=0, r=0, best=max(0, 0+0)=0, return 1.
depth(4): l=depth(6)=1, r=0, best=max(0, 1+0)=1, return 2.
depth(5): l=0, r=0, best=max(1, 0)=1, return 1.
depth(2): l=depth(4)=2, r=depth(5)=1, best=max(1, 2+1)=3, return 3.
depth(3): l=0, r=0, best=max(3, 0)=3, return 1.
depth(1): l=depth(2)=3, r=depth(3)=1, best=max(3, 3+1)=4, return 4.

return 4  (path 6 -> 4 -> 2 -> 1 -> 3 has 4 edges)

Complexity

• Time: O(n) — single post-order traversal.
• Space: O(h) recursion stack.

Edges vs nodes

Some statements of the problem return the path length in nodes (which is edges + 1). Read the spec carefully. The code is identical either way; only the final return value or the candidate update differs by one.