Diameter of Binary Tree

Every node offers one candidate: the deepest route from its left plus the deepest route from its right. The difference between the two approaches is how often you rediscover those depths.

Repeated height checks

For each node, compute the height of both subtrees from scratch. Their sum is the number of edges on the longest path whose highest point is that node. Then repeat the same work inside both children.

import sys
 
sys.setrecursionlimit(20_000)
 
 
def diameter_of_binary_tree(root: TreeNode | None) -> int:
    def height(node: TreeNode | None) -> int:
        if node is None:
            return 0
        return 1 + max(height(node.left), height(node.right))
 
    def best_below(node: TreeNode | None) -> int:
        if node is None:
            return 0
        through_node = height(node.left) + height(node.right)
        return max(through_node, best_below(node.left), best_below(node.right))
 
    return best_below(root)

Time O(n²) in a skewed tree because height walks almost the same long chain for every ancestor. Space O(h) for recursion, where h is the tree height.

One post-order pass

Post-order traversal handles both children before their parent. That is exactly the dependency here: once both child heights are known, update the candidate left + right, store 1 + max(left, right) for the parent, and never revisit that subtree.

def diameter_of_binary_tree(root: TreeNode | None) -> int:
    if root is None:
        return 0
 
    heights: dict[TreeNode, int] = {}
    stack = [(root, False)]
    best = 0
 
    while stack:
        node, expanded = stack.pop()
        if expanded:
            left = heights.get(node.left, 0)
            right = heights.get(node.right, 0)
            best = max(best, left + right)
            heights[node] = 1 + max(left, right)
            continue
 
        stack.append((node, True))
        if node.right is not None:
            stack.append((node.right, False))
        if node.left is not None:
            stack.append((node.left, False))
 
    return best

Why does left + right already count edges? A child subtree with height 1 contains one node, and reaching that node from the current one uses one edge. Each counted node below the meeting point corresponds to one edge on the joined path.

Time O(n) — each node enters and leaves the stack once. Space O(n) for stored heights and the explicit stack.

The familiar recursive post-order version uses O(h) call-stack space, but a 10,000-node line exceeds Python's default recursion limit. The explicit stack handles that input without changing interpreter settings.