The machine must find the length of the longest path between any two nodes in the tree, measured in edges. The path does not have to pass through the root — it can live entirely inside one subtree.
The key insight is that the longest path must pass through some node as its highest point, connecting a node in its left subtree to a node in its right subtree. The path length through a node is simply the height of its left subtree plus the height of its right subtree. So the machine can compute heights with a post-order DFS and, at each node, check whether the left-plus-right height beats the best seen so far.
The approach has three steps. First, recurse to compute the height of each child subtree. Second, at each node, compute left_height + right_height and update a global maximum if it is larger. Third, return 1 + max(left, right) as the node's height so the parent can continue the computation. Every node is visited once, so time is O(n) and space is O(h) for the call stack.
The trickiest edge case is the single-node tree: with no edges at all, its diameter is 0, and the global maximum must start at 0 rather than negative infinity. The machine also must remember the diameter can be in either subtree alone — the path through the root of that subtree will be evaluated when the recursion visits that node, which is why the global check runs at every node, not just the root.
def diameterOfBinaryTree(root):
diameter = 0
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter