Diameter of Binary Tree in DSA C++

Mental Model

The diameter is the longest path between any two nodes in the tree, which may or may not pass through the root.

Analogy: Imagine a network of roads connecting cities (nodes). The diameter is the longest possible route you can travel between two cities without repeating roads.

      1
     / \
    2   3
   / \
  4   5

Here, the diameter could be the path 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3.

Dry Run Walkthrough

Input: Binary tree: 1 with left child 2 and right child 3; 2 has children 4 and 5

Goal: Find the longest path between any two nodes in the tree

Step 1: Calculate height of node 4 (leaf)

Node 4 height = 0

Why: Leaf nodes have height 0, base case for recursion

Step 2: Calculate height of node 5 (leaf)

Node 5 height = 0

Why: Leaf nodes have height 0, base case for recursion

Step 3: Calculate height of node 2 using children 4 and 5

Node 2 height = max(0,0) + 1 = 1

Why: Height is max height of children plus one for current node

Step 4: Calculate height of node 3 (leaf)

Node 3 height = 0

Why: Leaf node base case

Step 5: Calculate diameter passing through node 2: left height + right height + 2 = 0 + 0 + 2 = 2

Diameter at node 2 = 2

Why: Longest path through node 2 is from leaf 4 to leaf 5

Step 6: Calculate diameter passing through node 1: left height + right height + 2 = 1 + 0 + 2 = 3

Diameter at node 1 = 3

Why: Longest path through root is from leaf 4 or 5 to leaf 3

Step 7: Compare diameters at all nodes and select maximum

Maximum diameter = 3

Why: Diameter is the longest path found anywhere in the tree

Result:

Diameter = 3 (path: 4 -> 2 -> 1 -> 3)

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
using namespace std;

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

class Solution {
public:
    int diameter = 0;

    int height(TreeNode* node) {
        if (!node) return -1; // base case: empty node height -1

        int leftHeight = height(node->left); // get left subtree height
        int rightHeight = height(node->right); // get right subtree height

        int pathThroughNode = leftHeight + rightHeight + 2; // path through current node
        diameter = max(diameter, pathThroughNode); // update max diameter

        return max(leftHeight, rightHeight) + 1; // height of current node
    }

    int diameterOfBinaryTree(TreeNode* root) {
        height(root); // start recursion
        return diameter;
    }
};

int main() {
    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 sol;
    cout << sol.diameterOfBinaryTree(root) << endl;
    return 0;
}

if (!node) return -1; // base case: empty node height -1

return -1 for null node to count edges correctly

int leftHeight = height(node->left); // get left subtree height

recursively get height of left subtree

int rightHeight = height(node->right); // get right subtree height

recursively get height of right subtree

int pathThroughNode = leftHeight + rightHeight + 2; // path through current node

calculate path length through current node

diameter = max(diameter, pathThroughNode); // update max diameter

update global diameter if current path is longer

return max(leftHeight, rightHeight) + 1; // height of current node

return height of current node for parent's calculation

height(root); // start recursion

start recursive height calculation from root

Output

3

Complexity Analysis

Time: O(n) because we visit each node once during height calculation

Space: O(h) where h is the tree height due to recursion stack

vs Alternative: Naive approach might calculate height repeatedly causing O(n^2) time; this approach calculates height once per node.

Edge Cases

Empty tree (root is null)

Diameter is 0 because there are no nodes

DSA C++

if (!node) return -1; // base case: empty node height -1

Single node tree

Diameter is 0 because no edges exist

DSA C++

if (!node) return -1; // base case: empty node height -1

Tree with only left or only right children

Diameter equals the height of the longest path (number of edges)

DSA C++

int pathThroughNode = leftHeight + rightHeight + 2; // path through current node

When to Use This Pattern

When asked for the longest path between any two nodes in a tree, use the diameter pattern which combines subtree heights to find the longest path.

Common Mistakes

Mistake: Returning 0 for null nodes instead of -1, causing off-by-one errors in diameter calculation
Fix: Return -1 for null nodes so edge counts are correct

Mistake: Calculating height separately multiple times causing inefficient O(n^2) time
Fix: Calculate height and diameter in the same recursion to keep O(n) time

Summary

Finds the longest path between any two nodes in a binary tree.

Use when you need the maximum distance between nodes, not just root to leaf.

The diameter is the max sum of left and right subtree heights plus two edges at any node.