Diameter of Binary Tree

Difficulty: Easy Source: NeetCode

Problem

Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.

Example 1: Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

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

Constraints:

The number of nodes in the tree is in the range [1, 10^4]

-100 <= Node.val <= 100

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree Height — The number of edges on the longest downward path from a node to a leaf
DFS (Post-order) — Computing answers bottom-up from leaves to root
Global State in Recursion — Using a variable outside the recursive call to track the answer

1. DFS with Global Max (Optimal)

The diameter at any node is the number of edges in its longest path through that node: left_height + right_height. We don’t know which node will give the global maximum, so we compute this at every node and track the best seen so far. Crucially, the DFS function returns the height (not the diameter) because that’s what the parent needs to compute its own diameter.

Algorithm

Initialize max_diameter = 0
Define a DFS function that returns the height of the subtree rooted at node:
- Base case: null node returns height 0
- Compute left_height and right_height recursively
- Update max_diameter = max(max_diameter, left_height + right_height)
- Return 1 + max(left_height, right_height) — the height of this subtree
Call DFS on root
Return max_diameter

Solution

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

def diameter_of_binary_tree(root):
    max_diameter = 0

    def dfs(node):
        nonlocal max_diameter
        if not node:
            return 0  # Height of null subtree

        left_height = dfs(node.left)
        right_height = dfs(node.right)

        # Diameter through this node = edges going left + edges going right
        max_diameter = max(max_diameter, left_height + right_height)

        # Return height of this subtree to the parent
        return 1 + max(left_height, right_height)

    dfs(root)
    return max_diameter

# --- helpers ---
def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

# --- tests ---
root1 = build_tree([1, 2, 3, 4, 5])
print(diameter_of_binary_tree(root1))  # 3

root2 = build_tree([1, 2])
print(diameter_of_binary_tree(root2))  # 1

root3 = build_tree([1])
print(diameter_of_binary_tree(root3))  # 0

# Skewed tree: 1 -> 2 -> 3 -> 4 -> 5
skewed = build_tree([1, 2, None, 3, None, 4, None, 5])
print(diameter_of_binary_tree(skewed))  # 4

Complexity

Time: O(n) — each node is visited exactly once
Space: O(h) — recursion stack depth equals tree height

Common Pitfalls

Thinking the diameter always passes through the root. It doesn’t. In a tree like [1,2,3,4,5,6,7], the diameter might be entirely within one subtree. That’s why we track the global max at every node.

Returning diameter instead of height from the DFS. The DFS helper must return height so the parent can compute its own diameter. If you return the diameter from DFS, you lose the information needed to propagate upward correctly.

Confusing edges vs nodes. The diameter is the number of edges, not nodes. A path with 4 nodes has 3 edges. Since we return 1 + max(left, right) from DFS (height in edges), and add left_height + right_height (both in edges), the math works out correctly without any adjustment.

Note Book