Diameter of Binary Tree

Intuition

The longest path that bends at a given node uses the tallest path going down its left child plus the tallest path going down its right child. If we know the height of the left subtree and the height of the right subtree, the candidate diameter through that node is simply leftHeight + rightHeight edges. So instead of recomputing heights repeatedly, we let the recursion return the height of each subtree while it bubbles back up. At each node we combine the two child heights to update a global best, then return 1 + max(leftHeight, rightHeight) so the parent can continue the accumulation. Because every node is visited once and does O(1) work, the whole computation is linear.

Algorithm walkthrough

1. 1Keep a shared variable best, initialized to 0, that will hold the largest diameter seen so far.
2. 2Define a helper height(node) that returns the number of edges on the longest downward path from node.
3. 3For a null node return 0; otherwise recurse to get leftHeight and rightHeight.
4. 4Update best = max(best, leftHeight + rightHeight), since a path can bend at this node.
5. 5Return 1 + max(leftHeight, rightHeight) so the parent gets this subtree's height.
6. 6After the traversal finishes, best holds the diameter in edges.

Implementation

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.best = 0

        def height(node):
            if not node:
                return 0
            left = height(node.left)
            right = height(node.right)
            self.best = max(self.best, left + right)
            return 1 + max(left, right)

        height(root)
        return self.best