• The number of nodes in the tree is in the range [1, 10⁴]
• -100 <= Node.val <= 100
• Length is counted in edges, not nodes
• The path need not include the root, and need not start or end at a leaf

A path is a route through the tree that does not visit any node twice. Because tree links only point downward, every path has a specific shape. It goes up for a while, reaches a highest node, and then goes down. The path can only bend once. If it dipped down and climbed back up, it would visit a node twice. (A straight downward path is a special case where the bend is at one end.) We want to find the longest path, measured in edges.

The main challenge is that there are many possible paths because any pair of nodes can form one. Also, the longest path does not have to go through the root. It can lie completely inside a subtree while the other side of the root has only one node.

Every path has exactly one highest node. This is the turning point, which is the closest node on the path to the root. Therefore, instead of checking every pair of endpoints, we can group the paths by their turning point. We can ask each node: what is the longest path that turns at you?

This question is easy to answer. A path that turns at node v goes as deep as possible into both the left and right subtrees of v. The longest possible distance on each side is equal to the height of that side. In terms of edges, reaching the deepest node in a subtree of height h takes exactly h edges from v. This includes one edge to enter the subtree, and h - 1 edges to go through it. So:

best path bending at v  =  height(v.left) + height(v.right)      [in edges]

Here, we count height in nodes. An empty subtree has a height of 0, which means that side has no nodes. Every path must turn at some node, and we can compute the best path for each node. Thus, the diameter is the largest value among all N nodes. We have replaced a search over all possible node pairs with a single calculation per node.

Let's check this formula on a simple case: a node with two leaf children. Both subtrees have a height of 1, which gives a path length of 1 + 1 = 2. Indeed, the path from leaf to node to leaf uses 2 edges. A single node has heights 0 + 0 = 0, which is correct because it has no edges.

We can write this directly in code: call a height helper for both sides of every node, add the heights, and update a running maximum.

def diameter(node):
    if node is None: return 0
    through = height(node.left) + height(node.right)   # each call re-walks a subtree
    return max(through, diameter(node.left), diameter(node.right))

This logic is correct, but it is too slow. The height helper traverses the entire subtree. Since we call it at every node, each node is measured again for every ancestor it has. The total work is the sum of all subtree sizes, which is roughly N × H. This is fine for a balanced tree, but it takes O(N²) time for a skewed tree (a chain). At N = 10⁴, this would require 100 million node visits.

This is wasteful because the main function is already traversing down the tree. The heights it calculates were already computed during previous steps.

Instead, we can do a single post-order traversal. When a node gets the heights of both children, it has all the information it needs for two tasks:

These are two different values, and the function can only return one of them. We must return the height so that the recursion can continue. Therefore, we store the path length (the bend) in a variable outside the helper function.

best = 0

def height(node):
    nonlocal best
    if node is None:
        return 0
    left  = height(node.left)
    right = height(node.right)
    best = max(best, left + right)     # the answer candidate: a path bending HERE
    return 1 + max(left, right)        # what the parent needs: a path passing THROUGH

height(root)
return best

Important Note: the returned value uses max, while the stored value uses +. Mixing these up is a common mistake. A path that continues up to the parent enters the node from above. It can only go down into one child subtree, because it cannot visit the same node twice. This is why we use max. A path that turns at this node can use both subtrees, which is why we use +. These are two different questions for a single node. This is why we return one value and track the other in a global variable.

Let's look at the third example, where the longest path does not pass through the root. The left child of the root is a leaf with a height of 1. The right child is node 3, which has two subtrees, each with a height of 3. Node 3 calculates a path of 3 + 3 = 6 and returns a height of 4. The root then calculates a path of 1 + 4 = 5, which is smaller. The running maximum stays 6, which is the path that turns at node 3, even though the root never uses it. We do not need any special code for paths that do not pass through the root. Checking every node as a turning point handles this automatically.

We visit each node once and do constant work at each step. This takes O(N) time, which is much faster than O(N × H). The space complexity is O(H) due to the recursion stack. The variable best is just a single integer, so it uses O(1) extra space.

This pattern is very common: when the value you need to return is different from the value you want to maximize, return the first value and track the second value in a separate variable. At each node, ask two questions: what does my parent need from me? and what is the longest path that turns at this node? You answer both through two separate channels — the return value carries the first, and an outside variable carries the second.