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.