Diameter of Binary Tree

The diameter through any single node equals the height of its left subtree plus the height of its right subtree — it does not have to pass through the root. The naive approach recomputes height from scratch at every node; the optimal one gets both the height and the diameter out of one pass.

Brute Force (height at every node)

Time O(n^2)Space O(h)

For each node, compute the height of its left and right subtrees independently, and take left height + right height as a diameter candidate. Take the max candidate over all nodes.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode | None) -> int:
        def height(node: TreeNode | None) -> int:
            if node is None:
                return 0
            return 1 + max(height(node.left), height(node.right))

        def diameter(node: TreeNode | None) -> int:
            if node is None:
                return 0
            through_node = height(node.left) + height(node.right)
            return max(through_node, diameter(node.left), diameter(node.right))

        return diameter(root)

Complexity: height is called from every node in diameter, and each call walks its whole subtree → O(n^2) in the worst case (e.g. a skewed tree). Recursion depth is the tree height → O(h) space.

Single Pass (height + diameter together)

OptimalTime O(n)Space O(h)

There is no need to call height separately: a single post-order DFS can return each node’s height and update a running best-diameter as a side effect, since by the time a node’s height is computed its children’s heights are already known.

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode | None) -> int:
        best = 0

        def height(node: TreeNode | None) -> int:
            nonlocal best
            if node is None:
                return 0
            left = height(node.left)
            right = height(node.right)
            best = max(best, left + right)
            return 1 + max(left, right)

        height(root)
        return best

Tracing root = [1,2,3,4,5] — heights bubble up from the leaves, and best updates whenever a node’s combined child heights beat the current record:

1 / 4

comparingseenresult

Leaves 4 and 5 return height 0 for their (None) children, so height(4) = height(5) = 1.

Complexity: height is computed exactly once per node, and best is updated in O(1) at each call → O(n) time. Space is still the recursion stack → O(h), matching the tree height.