Diameter of Binary Tree — Solution

Problem

Given a binary tree, find the length of its diameter — the longest path between any two nodes, measured in edges. The path doesn't have to pass through the root; it just has to stay within the tree.

[1,2,3,4,5]

• Input: root = [1, 2, 3, 4, 5]
• Output: 3
• Explanation: The longest path is 4 → 2 → 1 → 3, which crosses 3 edges.

A counter-example: if the tree is just a single node, the diameter is 0 — there are no edges.

Intuition

The diameter through any given node is the depth of its left subtree plus the depth of its right subtree. The challenge is that the longest path might bypass the root entirely, sitting deep in a subtree. So you need to check every node, not just the root. The efficient insight is that a depth-first traversal already computes subtree depths bottom-up — you can update the diameter as a side effect without any redundant work.

Approach 1 — Brute Force (Recompute Heights Per Node)

For every node, compute left and right subtree heights independently, then take the maximum across all nodes. Simple, but heights get recomputed many times.

1. Write a helper that returns the height of a subtree (number of edges to deepest leaf).
2. At the current node, compute left_height + right_height as the diameter candidate passing through it.
3. Recurse left and right to find any better path in those subtrees.
4. Return the max of the three candidates.

1class Solution:
2    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
3        def height(node: Optional[TreeNode]) -> int:
4            if not node:
5                return 0
6            return 1 + max(height(node.left), height(node.right))
7
8        if not root:
9            return 0
10
11        left_height = height(root.left)
12        right_height = height(root.right)
13        diameter_through_root = left_height + right_height
14
15        return max(
16            diameter_through_root,
17            self.diameterOfBinaryTree(root.left),
18            self.diameterOfBinaryTree(root.right),
19        )

Time: O(n²) — for each of the n nodes, height recomputes depths across the subtree below it. Space: O(h) — recursion stack depth equals tree height, O(n) in the worst case (skewed tree).

Approach 2 — Single DFS (Track Diameter as Side Effect)

Do one DFS pass. Each call returns the subtree's height, and before returning, it updates a global maximum with the local diameter (left depth + right depth). No node is visited more than once.

1. Initialize a variable to track the maximum diameter seen so far.
2. Run DFS: base case for null nodes returns 0 (no depth contribution).
3. Recursively get left and right subtree depths.
4. Update the global max with left_depth + right_depth (edges through this node).
5. Return 1 + max(left_depth, right_depth) so the parent gets the correct height.
6. After DFS completes, return the stored maximum.

1class Solution:
2    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
3        max_diameter = [0]  # list so the nested function can mutate it
4
5        def dfs(node: Optional[TreeNode]) -> int:
6            if not node:
7                return 0
8            left_depth = dfs(node.left)
9            right_depth = dfs(node.right)
10            # longest path through this node = left arm + right arm
11            max_diameter[0] = max(max_diameter[0], left_depth + right_depth)
12            # return height so the parent can extend the path upward
13            return 1 + max(left_depth, right_depth)
14
15        dfs(root)
16        return max_diameter[0]

Time: O(n) — each node is visited exactly once. Space: O(h) — recursion stack; O(n) in the worst case for a fully skewed tree.

Complexity Summary

Common Mistakes

• Assuming the diameter passes through the root — the longest path often lives entirely within a subtree. Checking only height(root.left) + height(root.right) will give the wrong answer for those cases.
• Returning the diameter instead of the height from the recursive helper — the helper must return height (depth to deepest leaf) so the parent can extend the path. The diameter update is a side effect, not the return value.
• Off-by-one between nodes and edges — a path through two nodes has 1 edge. The formula left_depth + right_depth counts edges correctly because each depth value represents the number of edges to the deepest descendant, not the number of nodes.
• Using a nonlocal integer in Python and forgetting that integers are immutable — the nonlocal keyword or a single-element list ([0]) is required; plain assignment inside a nested function creates a new local variable and silently leaves the outer one unchanged.
• Returning 0 instead of 0 at the null base case — the base case should return 0 (no edges contributed). Returning -1 or 1 shifts every depth value, making the diameter off by 2.

Related Problems

• Maximum Depth of Binary Tree — the diameter DFS is a direct extension of depth computation; start here if the pattern feels unfamiliar
• Binary Tree Maximum Path Sum — same side-effect pattern: return the best single-branch contribution to the parent while updating a global max for the through-path
• Balanced Binary Tree — also combines height computation with a global boolean check in one DFS pass
• Path Sum III — path-counting variant where you again track a running value through DFS and update a global count
• Longest Increasing Path in a Matrix — generalises "longest path in a DAG" to a grid; the memoised DFS mirrors the diameter logic