Diameter of Binary Tree — Longest Path Between Any Two Nodes

What is the Diameter of a Binary Tree? — Plain English

The diameter of a binary tree is the length of the longest path between any two nodes measured in number of edges. The path does not need to pass through the root. Think of the tree as a set of roads connecting nodes; the diameter is the longest road trip you can take without backtracking. For a tree with just a root, diameter = 0. For a tree where the deepest left subtree has height 3 and the deepest right subtree has height 2, the longest path through the root has 3+2=5 edges. But the actual diameter might be in a subtree entirely on the left side if that subtree itself spans a longer path. The key insight is that at every node, the longest path passing through that node equals left_height + right_height.

How Diameter of Binary Tree Works — Step by Step

Use a recursive DFS that returns the height of each subtree while updating a global maximum.

1. Define a helper dfs(node) that returns the height of the subtree rooted at node.
2. Base case: if node is None, return -1 (height of empty tree is -1, so a single leaf has height 0).
3. Recursively compute left_h = dfs(node.left) and right_h = dfs(node.right).
4. The diameter candidate at this node = left_h + right_h + 2 (add 2 for the two edges connecting to children).
5. Update global diameter: diameter = max(diameter, left_h + right_h + 2).
6. Return height of this node: max(left_h, right_h) + 1.
7. After DFS completes, return the global diameter.

Worked Example — Tracing the DFS

Tree: 1 / \ 2 3 / \ 4 5

DFS returns (height, updates diameter): 1. dfs(4): left=-1, right=-1. Diameter candidate: -1+-1+2=0. Update diameter=0. Return height=0. 2. dfs(5): left=-1, right=-1. Candidate=0. Return height=0. 3. dfs(2): left_h=0(from 4), right_h=0(from 5). Candidate=0+0+2=2. Diameter=2. Return height=max(0,0)+1=1. 4. dfs(3): left=-1, right=-1. Candidate=0. Return height=0. 5. dfs(1): left_h=1(from 2), right_h=0(from 3). Candidate=1+0+2=3. Diameter=max(2,3)=3. Return height=max(1,0)+1=2.

Final diameter=3. Path: 4→2→1→3 (or 5→2→1→3). Both have 3 edges.

Implementation

The solution uses a single DFS traversal. A class-level or nonlocal variable tracks the running maximum diameter. At each node, compute left and right subtree heights recursively, update the diameter with left_h + right_h + 2, then return max(left_h, right_h) + 1 as the node's height. The solution runs in O(n) time and O(h) stack space where h is the tree height (O(log n) balanced, O(n) worst case for skewed trees).

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):
    diameter = [0]  # use list to allow mutation in nested function

    def dfs(node):
        if node is None:
            return -1
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # path through this node has (left_h+1) + (right_h+1) edges
        diameter[0] = max(diameter[0], left_h + right_h + 2)
        return max(left_h, right_h) + 1

    dfs(root)
    return diameter[0]

# Build tree: 1->2->4,5 and 1->3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

print(diameter_of_binary_tree(root))  # 3 (path 4->2->1->3)

Frequently Asked Questions