Diameter of Binary Tree in DSA C++ - Deep Dive

Overview - Diameter of Binary Tree

What is it?

The diameter of a binary tree is the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of the path is counted by the number of edges between nodes. Finding the diameter helps understand the tree's widest spread.

Why it matters

Knowing the diameter helps in network design, biology, and computer science where the longest distance between points matters. Without this concept, we might miss critical bottlenecks or longest routes in tree-like structures, leading to inefficient designs or misunderstandings of data relationships.

Where it fits

Before this, you should understand binary trees and tree traversal methods like depth-first search. After this, you can explore tree balancing, advanced tree algorithms, or graph diameter concepts.

Mental Model

Core Idea

The diameter is the longest path between any two nodes, found by combining the longest paths through left and right subtrees at each node.

Think of it like...

Imagine a tree as a network of roads connecting towns (nodes). The diameter is the longest possible drive you can take between any two towns without retracing your steps.

       (root)
       /    \
   left     right
    |         |
 longest   longest
  path      path
    \       /
    longest combined path = diameter

Build-Up - 7 Steps

1

Foundation

Understanding Binary Tree Basics

Concept: Introduce the structure of a binary tree and how nodes connect.

A binary tree is a structure where each node has up to two children: left and right. Nodes store values and pointers to children. Traversing means visiting nodes in a certain order, like depth-first search (DFS).

Result

You can represent and traverse any binary tree, visiting all nodes systematically.

Understanding the tree's structure is essential before measuring distances or paths within it.

2

Foundation

What is Tree Diameter?

Concept: Define diameter as the longest path between any two nodes in the tree.

Diameter counts edges on the longest path connecting two nodes. This path might pass through the root or lie entirely in one subtree. It is not necessarily the height of the tree.

Result

You can distinguish diameter from height and understand it as a global longest path.

Knowing diameter is different from height prevents confusion and sets the stage for correct calculation.

3

Intermediate

Calculating Height of Subtrees

Concept: Learn to find the height (longest path from node to leaf) of left and right subtrees.

Height is found by recursively checking left and right children, then taking the maximum plus one. For example, height(node) = 1 + max(height(left), height(right)).

Result

You can compute the height of any node's subtree, a key step for diameter calculation.

Height calculation is the building block for understanding paths through nodes.

4

Intermediate

Combining Heights to Find Diameter

🤔Before reading on: Do you think the diameter always passes through the root node? Commit to yes or no.

Concept: Diameter at a node is the sum of left and right subtree heights; global diameter is the max over all nodes.

At each node, the longest path through it is left_height + right_height. We track the maximum such sum across all nodes. This covers paths passing through or not passing through the root.

Result

You can find the diameter by checking all nodes' combined subtree heights.

Understanding diameter as a max of combined subtree heights at any node unlocks the solution.

5

Intermediate

Implementing Diameter with DFS

🤔Before reading on: Will a single DFS traversal be enough to find the diameter? Commit to yes or no.

Concept: Use DFS to compute heights and update diameter in one pass.

Perform DFS from root. For each node, compute left and right heights recursively. Update a global diameter variable with left_height + right_height. Return height to parent.

Result

Diameter is found efficiently in O(n) time with one traversal.

Combining height calculation and diameter update in one DFS saves time and complexity.

6

Advanced

Handling Edge Cases and Empty Trees

🤔Before reading on: What should the diameter be for an empty tree? Commit to a number.

Concept: Consider empty trees and single-node trees in implementation.

If the tree is empty, diameter is zero. For single-node trees, diameter is zero because no edges exist. Code must handle null nodes gracefully.

Result

Your code correctly returns diameter for all tree sizes, including edge cases.

Accounting for edge cases prevents runtime errors and incorrect results.

7

Expert

Optimizing with Global State and Avoiding Recomputations

🤔Before reading on: Is it better to compute height and diameter separately or together? Commit to one approach.

Concept: Combine height and diameter calculation in one DFS to avoid repeated work.

Storing diameter in a global or external variable updated during DFS avoids recomputing heights multiple times. This optimization reduces time complexity and memory overhead.

Result

Your solution runs in linear time with minimal extra space.

Knowing how to merge computations efficiently is key for scalable tree algorithms.

Under the Hood

The algorithm uses recursion to explore each node's left and right children, calculating subtree heights. At each node, it sums these heights to find the longest path through that node. A global variable tracks the maximum sum found. This works because the longest path between any two nodes either passes through a common ancestor or lies entirely in one subtree.

Why designed this way?

This approach avoids checking all pairs of nodes explicitly, which would be very slow. By using heights and recursion, it leverages the tree's structure to find the diameter efficiently in one pass. Alternatives like brute force were rejected due to high time complexity.

          [Node]
          /    \
    [Left]    [Right]
      |          |
  heightL    heightR
      \        /
    sum = heightL + heightR
        |
    update diameter if sum > current max

Myth Busters - 4 Common Misconceptions

Quick: Does the diameter always pass through the root node? Commit to yes or no.

Common Belief: The diameter must always pass through the root node.

Reality: The diameter can be anywhere in the tree; it does not have to include the root.

Why it matters: Assuming it passes through the root can cause incorrect diameter calculations, missing longer paths in subtrees.

Quick: Is the diameter the same as the height of the tree? Commit to yes or no.

Common Belief: Diameter and height are the same because both measure longest paths.

Reality: Height measures longest path from root to leaf; diameter measures longest path between any two nodes, which can be longer.

Why it matters: Confusing these leads to underestimating the diameter and misunderstanding tree structure.

Quick: Can you find diameter by only counting nodes instead of edges? Commit to yes or no.

Common Belief: Diameter is the count of nodes on the longest path.

Reality: Diameter counts edges, which is one less than the number of nodes on the path.

Why it matters: Counting nodes instead of edges causes off-by-one errors in diameter results.

Quick: Does computing diameter require multiple traversals? Commit to yes or no.

Common Belief: You must traverse the tree multiple times to find diameter.

Reality: Diameter can be found in a single traversal by combining height calculation and diameter update.

Why it matters: Thinking multiple traversals are needed leads to inefficient code and slower performance.

Expert Zone

1

The diameter calculation can be adapted to weighted trees by summing edge weights instead of counting edges.

2

In very deep trees, recursion depth can cause stack overflow; iterative DFS or tail recursion optimization may be needed.

3

Tracking diameter during height calculation avoids redundant computations common in naive implementations.

When NOT to use

This approach is not suitable for graphs with cycles or non-tree structures. For general graphs, use algorithms like Floyd-Warshall or BFS-based diameter approximations.

Production Patterns

In production, diameter calculation helps optimize network latency, analyze biological phylogenies, and improve hierarchical data queries. Efficient single-pass DFS implementations are preferred for performance.

Connections

Tree Height

Diameter calculation builds on the concept of tree height by combining subtree heights.

Understanding height deeply enables grasping how diameter sums heights to find longest paths.

Graph Diameter

Diameter of a binary tree is a special case of graph diameter in acyclic graphs.

Learning tree diameter prepares you for more complex graph diameter problems involving cycles.

Longest Path Problem in Operations Research

Both find the longest path in a network, though operations research deals with weighted directed graphs.

Recognizing longest path problems across fields reveals shared algorithmic challenges and solutions.

Common Pitfalls

#1 Confusing diameter with height and returning height as diameter.

Wrong approach:

int diameter(Node* root) {
if (!root) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return 1 + max(leftHeight, rightHeight); // Incorrect: returns height, not diameter
}

Correct approach:

int diameter(Node* root) {
int diameter = 0;
heightAndDiameter(root, diameter);
return diameter;
}

int heightAndDiameter(Node* node, int& diameter) {
if (!node) return 0;
int leftHeight = heightAndDiameter(node->left, diameter);
int rightHeight = heightAndDiameter(node->right, diameter);
diameter = max(diameter, leftHeight + rightHeight);
return 1 + max(leftHeight, rightHeight);
}

Root cause:

Misunderstanding that diameter is the longest path between any two nodes, not just the height from root.

#2 Not updating diameter during recursion, causing incorrect results.

Wrong approach:

int height(Node* node) {
if (!node) return 0;
int left = height(node->left);
int right = height(node->right);
return 1 + max(left, right);
}

int diameter(Node* root) {
if (!root) return 0;
int leftDiameter = diameter(root->left);
int rightDiameter = diameter(root->right);
int rootDiameter = height(root->left) + height(root->right);
return max(rootDiameter, max(leftDiameter, rightDiameter));
} // Inefficient and recomputes heights multiple times

Correct approach:

int diameter(Node* root) {
int diameter = 0;
heightAndDiameter(root, diameter);
return diameter;
}

int heightAndDiameter(Node* node, int& diameter) {
if (!node) return 0;
int leftHeight = heightAndDiameter(node->left, diameter);
int rightHeight = heightAndDiameter(node->right, diameter);
diameter = max(diameter, leftHeight + rightHeight);
return 1 + max(leftHeight, rightHeight);
} // Efficient single pass

Root cause:

Failing to combine height and diameter calculations leads to repeated work and errors.

#3 Counting nodes instead of edges for diameter length.

Wrong approach:

diameter = leftHeight + rightHeight + 1; // Incorrect: counts nodes, not edges

Correct approach:

diameter = leftHeight + rightHeight; // Correct: counts edges between nodes

Root cause:

Confusing path length definitions causes off-by-one errors.

Key Takeaways

The diameter of a binary tree is the longest path between any two nodes, measured by edges.

It can be found efficiently by a single depth-first search that calculates subtree heights and updates diameter simultaneously.

Diameter does not always pass through the root; it can lie entirely within one subtree.

Handling edge cases like empty or single-node trees is essential for correct implementation.

Optimizing by combining computations avoids repeated work and improves performance.

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