Diameter of Binary Tree in DSA C++ - Build from Scratch

Diameter of Binary Tree

📖 Scenario: You are working on a program that analyzes tree structures. One important measure is the diameter of a binary tree, which is the longest path between any two nodes in the tree.This path may or may not pass through the root. You will build a program to find this diameter.

🎯 Goal: Build a C++ program that creates a binary tree, calculates the diameter of the tree, and prints the diameter value.

📋 What You'll Learn

Create a binary tree using a struct TreeNode with int val, TreeNode* left, and TreeNode* right.

Create a helper function to calculate the height of a node and update the diameter.

Calculate the diameter as the maximum number of nodes on the longest path between any two nodes.

Print the diameter value.

💡 Why This Matters

🌍 Real World

Calculating the diameter of a tree is useful in network design, biology (phylogenetic trees), and file system analysis to understand the longest communication or data path.

💼 Career

Understanding tree traversal and diameter calculation is important for software engineers working with hierarchical data, optimizing network latency, or solving complex algorithmic problems.

1

Create the binary tree structure and nodes

Define a struct TreeNode with int val, TreeNode* left, and TreeNode* right. Then create the root node with value 1, its left child with value 2, and its right child with value 3. Also create left child of node 2 with value 4 and right child of node 2 with value 5.

DSA C++

// Define TreeNode struct and create the binary tree nodes
// Your code here

Hint

Start by defining the TreeNode structure with the required members. Then create the nodes exactly as described.

2

Add a variable to store the diameter

Add an int variable called diameter and initialize it to 0 before the main() function.

DSA C++

#include 
using namespace std;

int diameter = 0; // Add diameter variable here

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

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);
    return 0;
}

Hint

Declare int diameter = 0; outside main() so it can be used globally.

3

Write a function to calculate height and update diameter

Write a function int height(TreeNode* node) that returns the height of the node. Inside it, calculate the height of left and right children recursively. Update the global diameter with the maximum of its current value and left_height + right_height + 1. Return the height as 1 + max(left_height, right_height).

DSA C++

#include 
using namespace std;

int diameter = 0;

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

int height(TreeNode* node) {
    // Your code here
}

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);
    return 0;
}

Hint

Use recursion to find heights of left and right subtrees. Update diameter with their sum plus one if larger. Return height as 1 plus the larger child height.

4

Calculate and print the diameter

Call the height function with root inside main() to update diameter. Then print the value of diameter.

DSA C++

#include 
using namespace std;

int diameter = 0;

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

int height(TreeNode* node) {
    if (node == nullptr) return 0;
    int left_height = height(node->left);
    int right_height = height(node->right);
    diameter = max(diameter, left_height + right_height + 1);
    return 1 + max(left_height, right_height);
}

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);
    height(root); // Calculate diameter
    cout << diameter << endl; // Print diameter
    return 0;
}

Hint

Call height(root); to update diameter. Then print diameter using cout.

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