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] — watch the heights bubble up from the leaves through the call stack, and best update every time a node’s combined child heights beat the current record.

Post-order DFS — height label under each node

1h:·

2h:·

3h:·

4h:·

5h:·

Call stack

height(1)

Running best

best diameter0

waiting for children

1 / 11

currentseenresult

Enter the root, node 1, and recurse left into node 2. Nothing is computed until both children come back.

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.

Diameter of Binary Tree

Brute Force (height at every node)

Single Pass (height + diameter together)

More Trees practice