Diameter of Binary Tree

def diameterOfBinaryTree(root):
    best = 0
    def height(node):
        nonlocal best
        if not node:
            return 0
        left = height(node.left)
        right = height(node.right)
        best = max(best, left + right)  # bend
        return 1 + max(left, right)     # pass up
    height(root)
    return best

Diameter of Binary Tree. Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes. The path doesn't have to pass through the root.

Here's the example: one on top, two and three below it, and four and five under two. The longest path runs from four, up through two and one, down to three: three edges. But in this tree, the longest path, five to six, bends at two and skips the root: four edges.

The naive way: at every node, measure the left and right heights from scratch, and add them. Each measurement walks a whole subtree, so a long, skewed tree costs n squared.

The key idea: every path bends at one highest node, and there its length is the left height plus the right height. So work up from the leaves. Each node takes its children's heights, updates the best with their sum, and passes one plus the bigger height up.

In code, an empty node has height zero. Get the left and right heights, update best with their sum, and return one plus the larger. After one pass, best is the answer.

Run it on the example. Four and five are leaves, so each returns one. At two, one plus one is two: best is two, and two returns two. Three returns one. At the root, two plus one is three, so best is three.

Every node is visited once, so the time is O of n. The recursion holds one path at a time, so the space is O of the tree's height.

Heights go up, left plus right at every bend, keep the best. That's Diameter of Binary Tree.