Longest path between any two nodes

For each node, the longest path that bends at that node is height(left) + height(right) in edges. Compute heights bottom-up and keep the best bend seen in an outer variable. One post-order walk: O(n) time, O(h) stack.

The function returns one thing (height) but records another (best path): a common tree pattern.

Calling a separate height function at every node is O(n²) on a chain.

Count edges, not nodes, unless the question says otherwise.

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

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

Common mistakes

• Assuming the longest path passes through the root.
• Mixing node counts and edge counts between the height and the answer.

Say 'return height, record the best bend' before writing. It shows you know the pattern, not just this answer.

Follow-up questions

Think of your answer first, then open the hint.

1. What if nodes have weights?

   Show hint

   Track the heaviest downward path instead of height; same structure.

2. How would you find the path in a general tree?

   Show hint

   Two BFS passes: farthest node from any node, then farthest from that.