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.

Practice

1. What does the diameter of a binary tree represent?

easy

A. The longest path between any two nodes in the tree

B. The height of the tree

C. The number of leaf nodes

D. The total number of nodes in the tree

Solution

1. Step 1: Understand the diameter definition

   The diameter is the longest path between any two nodes, not just from root to leaf.

2. Step 2: Differentiate from height and node count

   Height is longest root-to-leaf path; node count and leaf count are unrelated to diameter.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option A

4. Quick Check:

   Diameter = longest node-to-node path [OK]

Hint: Diameter is longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with tree height
• Thinking diameter counts nodes instead of edges
• Assuming diameter is number of leaf nodes

2. Which of the following is the correct C++ function signature to compute the diameter of a binary tree node?

easy

A. int diameter(TreeNode& root);

B. void diameter(TreeNode root);

C. int diameter(TreeNode root);

D. int diameter(TreeNode* root);

Solution

1. Step 1: Understand pointer usage in tree nodes

   Binary trees are usually handled with pointers to nodes, so TreeNode* is correct.

2. Step 2: Check return type and parameter correctness

   Diameter returns an int, and parameter should be pointer, not value or reference for typical tree traversal.

3. Final Answer:

   int diameter(TreeNode* root); -> Option D

4. Quick Check:

   Pointer parameter with int return [OK]

Hint: Use pointer parameter and int return type [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using void return type instead of int
• Passing node by reference unnecessarily

3. What is the output of the following code snippet computing diameter?

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

int height(TreeNode* root) {
  if (!root) return 0;
  return 1 + std::max(height(root->left), height(root->right));
}

int diameter(TreeNode* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  return std::max(leftHeight + rightHeight, std::max(leftDiameter, rightDiameter));
}

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);
  std::cout << diameter(root);
  return 0;
}

medium

A. 6

B. 4

C. 3

D. 5

Solution

1. Step 1: Calculate heights of left and right subtrees

   Left subtree height: max height of nodes 2->4 or 2->5 is 2; right subtree height (node 3) is 1.

2. Step 2: Calculate diameter candidates and choose max

   Diameter candidates: leftHeight + rightHeight = 2 + 1 = 3; leftDiameter and rightDiameter are computed recursively. LeftDiameter is 2 (path 4-2-5), rightDiameter is 0. Max is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Sum left and right subtree heights for diameter [OK]

Common Mistakes:

• Confusing height with diameter
• Counting nodes instead of edges
• Ignoring recursive diameter calls

4. Identify the bug in this diameter function and select the fix:

int diameter(TreeNode* root) {
  if (!root) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  int leftDiameter = diameter(root->left);
  int rightDiameter = diameter(root->right);
  return leftHeight + rightHeight;
}

medium

A. Return max of leftDiameter and rightDiameter only

B. Return max of leftHeight + rightHeight and leftDiameter, rightDiameter

C. Return sum of leftDiameter and rightDiameter

D. Return height of root node

Solution

1. Step 1: Analyze current return statement

   Currently returns only leftHeight + rightHeight, ignoring recursive diameters from subtrees.

2. Step 2: Correct return to consider all diameter candidates

   Diameter is max of leftHeight + rightHeight, leftDiameter, and rightDiameter.

3. Final Answer:

   Return max of leftHeight + rightHeight and leftDiameter, rightDiameter -> Option B

4. Quick Check:

   Include all diameter candidates [OK]

Hint: Return max of height sum and subtree diameters [OK]

Common Mistakes:

• Ignoring recursive diameter calls
• Returning sum of diameters incorrectly
• Returning height instead of diameter

5. Given a binary tree where each node has a value, how would you modify the diameter function to return the maximum sum of node values on any path between two nodes instead of the number of edges?

hard

A. Change height function to return max sum of node values and update diameter to use sums instead of heights

B. Use the same diameter function but multiply the result by node values

C. Calculate diameter normally and add all node values in the tree

D. Return the maximum node value in the tree as diameter

Solution

1. Step 1: Modify height to return max sum of node values

   Instead of counting edges, height returns max sum from node to leaf including node values.

2. Step 2: Update diameter to use sums from left and right subtrees

   Diameter becomes max of left sum + right sum and recursive diameters, reflecting max path sum.

3. Final Answer:

   Change height function to return max sum of node values and update diameter to use sums instead of heights -> Option A

4. Quick Check:

   Use sums in height and diameter for max path value [OK]

Hint: Use sums in height and diameter for max path value [OK]

Common Mistakes:

• Multiplying diameter by node values incorrectly
• Adding all node values regardless of path
• Returning max node value instead of path sum