Binary Tree Diameter — Root-Only Calculation Fails Silently

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.

Naive O(n²) Approach — Why It Fails and How to Improve

Before diving into the optimal O(n) solution, it's instructive to examine the naive approach that many developers write first. The naive solution computes the height of each node separately for every node, leading to O(n²) time. For each node, it calls a separate height function that traverses all descendants. The diameter candidate is simply left_height(node) + right_height(node), and we take the maximum across all nodes. While this is conceptually simple, it's painfully slow for large trees. Each height computation takes O(n) in the worst case, and we do it for all n nodes, resulting in O(n²). The optimal solution solves the problem in a single DFS by combining height calculation with diameter tracking.

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def diameter_naive(root):
    if root is None:
        return 0
    # Compute height of left and right subtrees
    left_h = height(root.left) + 1 if root.left else 0
    right_h = height(root.right) + 1 if root.right else 0
    # Diameter through root
    through_root = left_h + right_h
    # Recur for subtrees
    left_diameter = diameter_naive(root.left)
    right_diameter = diameter_naive(root.right)
    return max(through_root, left_diameter, right_diameter)

# Usage with tree from earlier example
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_naive(root))  # Correctly prints 3, but O(n²)

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.

Visual Tree Diagram — Diameter Path Highlighted

The diagram below shows the tree used in the worked example. The diameter path from node 4 to node 3 is highlighted in red. This path goes up from 4 to 2, then to root 1, then down to 3. It covers exactly 3 edges. Understanding how the path traverses through the highest node (the root in this case, but it could be any node) reinforces the "every node as potential apex" concept.

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)

C++ Implementation

The C++ implementation follows the same logic: a recursive helper returns height while updating a diameter variable passed by reference. The key difference is the explicit use of std::max and the struct for TreeNode. C++ recursion depth is also limited by the call stack; for very deep trees, consider an iterative approach using a stack of pairs or a post-order traversal with parent pointers.

#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        height(root, diameter);
        return diameter;
    }
private:
    int height(TreeNode* node, int& diameter) {
        if (node == nullptr) return -1;
        int left_h = height(node->left, diameter);
        int right_h = height(node->right, diameter);
        diameter = max(diameter, left_h + right_h + 2);
        return max(left_h, right_h) + 1;
    }
};

// Usage:
// TreeNode* root = new TreeNode(1);
// root->left = new TreeNode(2);
// root->right = new TreeNode(3);
// root->left->left = new TreeNode(4);
// root->left->right = new TreeNode(5);
// Solution().diameterOfBinaryTree(root); // returns 3

Top-Down Recursion Approach — Alternative Implementation Pattern

Instead of using a global variable, the top-down approach returns a pair (height, diameter) from each node. This is a more functional style, avoids global state, and is easier to parallelize (though tree recursion doesn’t parallelize trivially). The function computes the left and right pair recursively, then constructs the current node's pair: height = max(left.height, right.height) + 1, diameter = max(left.diameter, right.diameter, left.height + right.height + 2). The top-down pattern is especially useful when the problem can be expressed as combining results from children without side effects.

def diameter_top_down(root):
    def dfs(node):
        if node is None:
            return (-1, 0)  # (height, diameter)
        left_h, left_d = dfs(node.left)
        right_h, right_d = dfs(node.right)
        height = max(left_h, right_h) + 1
        diameter = max(left_d, right_d, left_h + right_h + 2)
        return (height, diameter)
    return dfs(root)[1]

# Usage same as before
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_top_down(root))  # 3

Edge Cases and Production Pitfalls

Advantages and Disadvantages of the O(n) Diameter Algorithm

The algorithm is optimal for the problem. The disadvantages are manageable with careful implementation: use iterative approach for deep trees, and validate base cases through unit tests.

Practice Problems

Reinforce your understanding by solving these related problems:

• [LeetCode 543 — Diameter of Binary Tree](https://leetcode.com/problems/diameter-of-binary-tree/) — The classic problem, identical to this article.
• [LeetCode 687 — Longest Univalue Path](https://leetcode.com/problems/longest-univalue-path/) — Similar concept but path must consist of nodes with the same value.
• [LeetCode 124 — Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/) — Uses similar pattern but with node values.
• [LeetCode 1522 — Diameter of N-Ary Tree](https://leetcode.com/problems/diameter-of-n-ary-tree/) — Extend the idea to trees with multiple children.
• [GeeksforGeeks — Diameter of a Tree](https://www.geeksforgeeks.org/diameter-of-a-binary-tree/) — Additional explanations and variations.
• [LeetCode 298 — Binary Tree Longest Consecutive Sequence](https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/) — Another path-length problem that uses DFS with state tracking.