Find the Longest Path in a Tree: From Measuring at Every Node to One Pass

Asking every node for the heights of its two subtrees walks the lower nodes again and again; returning each height once lets one pass find the longest path.

The longest path in a binary tree can be found in one pass by having each call return its height and record the path that bends through it. That path is the tree's diameter: the most edges on a path between any two nodes. The tree has root 30, with children 14 and 41; 14 has children 9 and 21, and below them hang 5 and 2 on one side and 26 and 24 on the other. The longest path runs from 2 up to 14 and down to 24, six edges, and it does not pass through the root.

The brute force measures at every node. A path that bends at a node goes down its left subtree and down its right, so its length is the left child's height plus the right child's height plus the two edges to them. Visiting each node and calling a height function on both children finds every such path, and the largest is the answer. The repeated work is in the height calls: the call at 30 walks every node below it, the call at 14 walks most of them again, and so on down, so on a tree shaped like a chain the cost is n − 1 + n − 2 + … + 1, which is O(n²). Every height the brute force needs is already known by the child below, and a child that returned its height would save the walk.

Measuring at every node against one pass

Measuring at every nodeO(n²) on a chain

At each node, call height on both children and compare the bent path with the best. The height calls walk each subtree again for every node above it.

One passO(n) time, O(h) stack

Each call returns its height to its parent and records left height + right height + 2 in a best-so-far. Every node is visited once.

In the one pass, each node's note gives the height it returned and the bent path it recorded. The best-so-far is 6, recorded at 14; the root records only 5, because its left side reaches down 4 edges and its right side 1.

Heights returned and paths recorded in one pass

30, returns height 4, records path 5
- 14, returns height 3, records path 6, the longest
  - 9, returns height 2, records path 2
    - 5, returns height 1, records path 1
      - 2, leaf: returns height 0, records path 0
      - null, empty right child, returns −1
    - null, empty right child, returns −1
  - 21, returns height 2, records path 2
    - null, empty left child, returns −1
    - 26, returns height 1, records path 1
      - 24, leaf: returns height 0, records path 0
      - null, empty right child, returns −1
- 41, leaf: returns height 0, records path 0

The listing runs both versions on this tree and counts the nodes each one visits.

longest_path.pypy

class Node:
    def __init__(self, value: int, left: Node | None = None, right: Node | None = None) -> None:
        self.value = value
        self.left = left
        self.right = right

visited: list[int] = []


def height(node: Node | None) -> int:
    if node is None:
        return -1
    visited.append(node.value)
    return max(height(node.left), height(node.right)) + 1


def longest_by_measuring(node: Node | None) -> int:
    if node is None:
        return 0
    through = height(node.left) + height(node.right) + 2
    return max(through, longest_by_measuring(node.left), longest_by_measuring(node.right))


def longest_in_one_pass(root: Node | None) -> int:
    best = 0

    def walk(node: Node | None) -> int:
        nonlocal best
        if node is None:
            return -1
        visited.append(node.value)
        left = walk(node.left)
        right = walk(node.right)
        best = max(best, left + right + 2)
        return max(left, right) + 1

    walk(root)
    return best


tree = Node(30, Node(14, Node(9, Node(5, Node(2))), Node(21, None, Node(26, Node(24)))), Node(41))
longest = longest_by_measuring(tree)
print(f"measuring at every node: longest {longest}, height calls visited {len(visited)} nodes")
visited.clear()
longest = longest_in_one_pass(tree)
print(f"one pass:                longest {longest}, visited {len(visited)} nodes")

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

measuring at every node: longest 6, height calls visited 20 nodes
one pass:                longest 6, visited 9 nodes

Both find 6. The height calls of the brute force visit 20 nodes on a tree of 9, and the one pass visits each node once; on a chain of 500 nodes the height calls visit 124,750. The one pass is O(n) time and O(h) space for the recursion, which is O(n) on a chain and O(log n) on a balanced tree. Returning the height and recording the path is also why the root's own path, 5, does not hide the longer one lower down.

← → move through sections and cards