Diameter of a binary tree: join two downward paths

The tempting shortcut is to measure the farthest leaf on each side of the root and add the distances. That misses paths which turn at a node farther down. A useful example should make that shortcut fail, not accidentally reward it.

A longest path that misses the root#

The numbers below identify nodes; they are not weights and need not obey search-tree ordering.

         99
        /
       10
      /  \
     5    15
    /       \
   2         20

The path 2 → 5 → 10 → 15 → 20 has five nodes and four edges. Any path starting at 99 reaches at most three edges. The diameter therefore turns at 10, not at the root.

Use a height convention that is easy to calculate: an empty subtree has height 0, and a leaf has height 1. At node 10, both child subtrees have height 2. Reaching the deepest left leaf from 10 takes two edges; reaching the deepest right leaf takes another two. Their sum, 2 + 2, is already an edge count. Do not add one for the turning node.

The problem definition counts edges and allows the longest path to miss the root. Our example deliberately makes both conditions visible.

Try it: count the longest path in edges

Choose an illustrative tree. The longest path may stay below the root.

Choose a case One node RA — R — BR above A; D–B–A–C–E below it

Compute children before their parent#

A parent needs its children’s heights first. That is postorder traversal: finish the children before calculating the parent. This complete Python 3.10+ version uses an explicit stack, so a tall tree does not require one Python call frame per level.

from __future__ import annotations
from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: int
    left: Node | None = None
    right: Node | None = None

def diameter(root: Node | None) -> int:
    if root is None:
        return 0
    heights: dict[Node, int] = {}
    pending: list[tuple[Node, bool]] = [(root, False)]
    best = 0
    while pending:
        node, children_done = pending.pop()
        if not children_done:
            pending.append((node, True))
            if node.right is not None:
                pending.append((node.right, False))
            if node.left is not None:
                pending.append((node.left, False))
            continue
        left = heights.get(node.left, 0)
        right = heights.get(node.right, 0)
        best = max(best, left + right)
        heights[node] = 1 + max(left, right)
    return best

example = Node(99, Node(10, Node(5, Node(2)), Node(15, None, Node(20))))
assert diameter(example) == 4
assert diameter(None) == 0
assert diameter(Node(7)) == 0
assert diameter(Node(1, Node(2, Node(3)))) == 2
assert diameter(Node(1, Node(2), Node(3))) == 2

The second stack entry for a node says, “Its children will have been processed when you return here.” Only that second visit calculates a height. eq=False keeps nodes distinct by object identity: two nodes with the same displayed value are still different places in the tree.

The dictionary records one height per node. This implementation uses O(n) auxiliary memory, not O(h) overall: the stack alone is height-bounded, but the saved heights are not. A recursive version can keep heights only in call frames and use O(h) auxiliary space, at the cost of the interpreter’s recursion limit. See the Python recursion-error guide before choosing recursion for an unbounded input.

Why one pass is enough#

Every simple path in a rooted tree has one highest node. At that node the path either joins a downward left arm and a downward right arm, or uses only one arm. Empty arms have length zero. The calculation tries the longest available arms at every possible turning node, so it cannot miss the longest path.

Each node is pushed a bounded number of times, and its already-computed child heights are read once. The total work is O(n). Recomputing a complete subtree height separately at every node can instead become O(n²) on a chain. The saved heights avoid that repeated traversal.

This measures an unweighted, finite binary tree. It assumes no cycles and no node shared by multiple parents. It returns a length, not the actual list of nodes on the winning path. Recovering that path requires remembering the best endpoints or downward choices. Weighted edges need distance sums rather than these node heights.

To separate the two questions, validate a binary search tree next: validation examines the values and ancestor bounds, whereas diameter depends only on the connections. The traversal guide shows why postorder is the useful processing order here.

Questions people also ask

2 QUESTIONS

▸ Is the diameter measured in nodes or edges?

This page and the linked LeetCode problem count edges. A nonempty path containing five nodes has four edges. Check the contract before adapting the code to a problem that counts nodes instead.

▸ Is the diameter twice the height?

Not generally. The longest path can have unequal arms or lie below the root. Compute the best left-height plus right-height sum at every node rather than doubling one root height.