The longest path anywhere in the tree

The diameter of a binary tree is the number of edges on the longest path between any two nodes. That path does not have to go through the root.

Worked example#

      1
     / \
    2   3
   / \
  4   5

The longest path runs 4 -> 2 -> 5, or 4 -> 2 -> 1 -> 3. Both are 3 edges, so the diameter is 3.

The idea#

The trap here is assuming the longest path goes through the root. It often does not: hang a long chain off one grandchild and the best path never touches the top.

So ask a different question. For each node, what is the longest path whose highest point is that node? That path goes down into the left subtree as far as it can, up to this node, and down into the right subtree as far as it can. Its length is:

depth of the left subtree + depth of the right subtree

Every path in the tree has exactly one highest node, so if you compute that for every node, the biggest is the diameter.

Doing it in one pass#

You need the depth of each subtree, and you need to combine two depths at each node. That is one recursion doing two jobs: it returns the depth to its parent, and on the way it records the best it has seen.

depth(node):
    if node is nothing: return 0
    l = depth(node.left)
    r = depth(node.right)
    best = max(best, l + r)      # the answer, recorded on the way up
    return 1 + max(l, r)         # the depth, returned to the parent

Two lines, two different jobs. Confusing them is the usual bug: returning l + r instead of 1 + max(l, r) gives a number that means nothing to the parent.

This "return one thing, record another" shape comes back constantly in tree problems, and it is worth recognising it here where it is small.

Constraints#

• 0 <= number of nodes <= 100000

About the input#

The tree is written level by level with null for a missing child, the count first.