Diameter of Binary Tree

Problem

Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes in the tree. The path may or may not pass through the root, and it never repeats a node.

Key detail: the answer counts edges, not nodes — a path through k nodes has length k − 1.

Examples

Example 1

Input:  root = [1,2,3,4,5]

        1
       / \
      2   3
     / \
    4   5

Output: 3

One longest path is 4 → 2 → 1 → 3 (equally 5 → 2 → 1 → 3): 4 nodes, 3 edges.

Example 2

Input:  root = [1,2]
Output: 1

Only one edge exists.

Example 3

        1
       /
      2
     / \
    3   4
   /     \
  5       6

Output: 4

The longest path 5 → 3 → 2 → 4 → 6 bends at node 2 and never touches the root.

Constraints

• The number of nodes is in [1, 10^4] — O(n) is expected; the O(n^2) recompute-heights approach is the brute force to beat.
• -100 <= Node.val <= 100 — values are irrelevant; only shape matters.

Think about it first

TL;DR

Single post-order DFS that returns height while updating a running max of left_height + right_height — O(n) time, O(h) space.

Approach 1 — Brute force: recompute heights at every node

The naive idea straight from the definition: every path bends at some highest node, and the longest path bending at node v uses height(v.left) + height(v.right) edges. So visit every node, compute both subtree heights from scratch, and take the max.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def height(node: Optional[TreeNode]) -> int:
            """Edges on the longest downward chain from node."""
            if not node or (not node.left and not node.right):
                return 0
            return 1 + max(height(node.left), height(node.right))

        def edges_below(node: Optional[TreeNode], child: Optional[TreeNode]) -> int:
            return 0 if not child else 1 + height(child)

        if not root:
            return 0
        here = edges_below(root, root.left) + edges_below(root, root.right)
        return max(here,
                   self.diameterOfBinaryTree(root.left),
                   self.diameterOfBinaryTree(root.right))

Complexity: O(n^2) time in the worst case — each node’s height is recomputed once per ancestor (a skewed tree with n = 10^4 does ~5·10^7 visits). O(h) space. The constraints allow up to 10^4 nodes precisely to make this feel slow and push you to one pass.

Approach 2 — One post-order DFS (height + running max)

The insight: the brute force runs two recursions over the same nodes — one to check every bend point, one to measure heights. Post-order DFS (the classical traversal that finishes both children before the node) already holds both child heights when it visits a node, so it can update the diameter and return the height in a single visit. Every node is considered as a potential bend point exactly once.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


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

        def dfs(node: Optional[TreeNode]) -> int:
            """Return #edges on the longest downward chain from node."""
            if not node:
                return -1          # so a leaf gets 1 + (-1) = 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.best = max(self.best, left + right + 2)
            return 1 + max(left, right)

        dfs(root)
        return self.best

(Convention note: dfs(None) = -1 makes a leaf’s chain length 0 edges, and the bend at node costs left + right + 2 edges — one edge down each side. The equivalent node-counting convention returns 0 for None and uses left + right.)

Walkthrough on [1,2,3,4,5] (example 1):

Answer: 3 — the path 4 → 2 → 1 → 3.

Complexity: O(n) time (each node visited once), O(h) recursion space — O(n) worst case on a skewed tree.

Approach 3 — Iterative post-order with an explicit stack

The insight: the same bottom-up computation runs without recursion if you process a node only after both children are done, caching each finished subtree’s height in a dict — useful when h could exceed Python’s ~1000-frame default recursion limit.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, Dict


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        heights: Dict[Optional[TreeNode], int] = {None: -1}
        best = 0
        stack = [(root, False)] if root else []
        while stack:
            node, visited = stack.pop()
            if visited:
                left = heights[node.left]
                right = heights[node.right]
                best = max(best, left + right + 2)
                heights[node] = 1 + max(left, right)
            else:
                stack.append((node, True))
                if node.left:
                    stack.append((node.left, False))
                if node.right:
                    stack.append((node.right, False))
        return best

Walkthrough on [1,2] (example 2): 1 is deferred, 2 pops as a leaf → heights[2] = 0; then 1 re-emerges with left = 0, right = -1 → best = 0 + (-1) + 2 = 1. Answer 1.

Complexity: O(n) time, O(n) space for the stack and height map.

Common pitfalls

• Counting nodes instead of edges — the classic off-by-one; a single node has diameter 0, not 1.
• Assuming the longest path passes through the root — example 3 in the question bends at a mid-tree node.
• Returning left + right + 2 from dfs instead of 1 + max(left, right) — the value passed to the parent must be a single downward chain, not the bent path.
• Forgetting to seed the leaf/None convention consistently (None → -1 with +2 at the bend, or None → 0 counting nodes) — mixing the two inflates the answer.

Pattern takeaway

This is the archetype of the “global answer, local recursion” tree pattern: the recursion returns the quantity a parent can extend (a single downward height), while a side-channel maximum captures the quantity that can’t be extended (the bent path). Whenever a tree problem asks for the best path/sum/width that may bend at any node, compute per-node combinations in post-order and keep the running best outside the return value.