Find the Diameter of a Binary Tree in C++

Introduction

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of a path is measured by the number of edges between the nodes.

To find the diameter, we need to calculate the longest path in the tree. This path will either:

• Pass through the root (left subtree height + right subtree height + 1), or
• Be confined entirely within the left or right subtree.

Program Structure

The program will follow these steps:

1. Define a TreeNode structure representing each node in the binary tree.
2. Write a recursive function findDiameter that calculates the diameter of the binary tree.
3. In the process, maintain the height of the tree and calculate the diameter at each node.

Code Implementation

// C++ program to find the diameter of a binary tree

#include <iostream>
using namespace std;

// Define the structure of a tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    // Constructor to initialize the tree node
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// Helper function to calculate the diameter and height of the tree
int findDiameter(TreeNode* root, int& diameter) {
    if (root == NULL) return 0;  // Base case: if node is NULL, height is 0

    // Recursively find the height of the left and right subtrees
    int leftHeight = findDiameter(root->left, diameter);
    int rightHeight = findDiameter(root->right, diameter);

    // Calculate the potential diameter at the current node
    int currentDiameter = leftHeight + rightHeight;

    // Update the overall diameter if the current diameter is larger
    diameter = max(diameter, currentDiameter);

    // Return the height of the current node (1 + max of left and right heights)
    return 1 + max(leftHeight, rightHeight);
}

// Function to find the diameter of the binary tree
int diameterOfBinaryTree(TreeNode* root) {
    int diameter = 0;  // Initialize diameter
    findDiameter(root, diameter);  // Call helper function
    return diameter;  // Return the final diameter
}

// Helper function to insert a new node into the binary tree (for testing purposes)
TreeNode* insert(TreeNode* node, int val) {
    if (node == NULL) return new TreeNode(val);  // If the tree is empty, create a new node

    // Otherwise, recursively insert the value into the left or right subtree
    if (val < node->val)
        node->left = insert(node->left, val);
    else
        node->right = insert(node->right, val);

    return node;
}

int main() {
    /* Sample Binary Tree:
              1
            /   \
           2     3
          / \     
         4   5   
    */

    // Creating the binary tree
    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);

    // Finding the diameter of the binary tree
    int diameter = diameterOfBinaryTree(root);

    // Output the result
    cout << "The diameter of the binary tree is: " << diameter << endl;

    return 0;
}

Explanation

Let’s break down the program:

1. TreeNode structure: This structure represents a node in the binary tree. Each node stores a value val and pointers to its left and right children.
2. findDiameter function: This is the recursive function that calculates the height of the tree while also updating the diameter. It recursively calculates the height of the left and right subtrees, and at each node, checks if the current diameter (left height + right height) is greater than the maximum diameter so far.
3. diameterOfBinaryTree function: This function initializes the diameter to 0 and calls the helper function findDiameter to compute the actual diameter of the tree.
4. insert function: This helper function is used to build the binary tree by inserting nodes. This part is used only for testing purposes and is optional based on how the tree is constructed.

How the Algorithm Works

The algorithm is based on the fact that the diameter of the tree at any node is the sum of the heights of its left and right subtrees. The recursion terminates when the node is NULL (base case), at which point we return a height of 0.

The recursion ensures that each node contributes to the height calculation and checks if the path through that node offers a larger diameter. The maximum diameter across all nodes is maintained and returned at the end.

Sample Output

If you run the above program with the example binary tree, the output will be:

The diameter of the binary tree is: 3

In the sample binary tree, the longest path (diameter) passes through nodes 4, 2, and 5, resulting in a diameter of 3 edges.

Conclusion

The diameter of a binary tree is the longest path between any two nodes in the tree. This path can pass through the root or be confined within one of the subtrees. The time complexity of the algorithm is O(N), where N is the number of nodes in the tree, as each node is visited once. The space complexity is O(H), where H is the height of the tree due to the recursive calls.

This approach ensures that the diameter is calculated efficiently while also determining the height of the tree in a single traversal.