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], so O(n) is expected; the O(n^2) recompute-heights approach is the brute force.
• -100 <= Node.val <= 100. Values do not matter; only the tree shape does.

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

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. 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


def diameterOfBinaryTree(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,
               diameterOfBinaryTree(root.left),
               diameterOfBinaryTree(root.right))

Complexity: O(n^2) time in the worst case, because each node’s height is recomputed once per ancestor (a skewed tree with n = 10^4 does ~5·10^7 visits). O(h) space. With up to 10^4 nodes, a skewed tree makes this too slow, which is the point of the constraint.

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 and one to measure heights. Post-order DFS finishes both children before the node, so it already holds both child heights when it visits a node. It can update the diameter and return the height in a single visit, and every node is considered as a 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


def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
    best = 0

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

    dfs(root)
    return 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):

flowchart TD
    N1((1)) --> N2((2))
    N1 --> N3((3))
    N2 --> N4((4))
    N2 --> N5((5))

The longest path is 4 → 2 → 1 → 3, which bends at node 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. This helps 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


def diameterOfBinaryTree(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 “global answer, local recursion” tree pattern: the recursion returns the quantity a parent can extend (a single downward height), while a separate maximum captures the quantity that cannot be extended (the bent path). Whenever a tree problem asks for the best path, sum, or width that may bend at any node, compute per-node combinations in post-order and keep the running best outside the return value.