Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in the tree. It may or may not pass through the root.

Examples

Example 1:

Input : root = [1, 2, 3, 4, 5]
Output : 3

Explanation : The path length between node 4 and 3 is of length 3.
There are other ways to reach the solution.

Example 2:

Input : root = [1, 2, 3, null, 4, null, 5]
Output : 4

Explanation : The path length between node 4 and 5 is of length 4.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

To determine the diameter of a binary tree, consider each node as a potential Curving Point in the path that forms the diameter. This Curving Point represents the node at the maximum height along the diameter path, where the path transitions between ascending and descending. The diameter at a particular Curving Point is calculated by adding the height of the left subtree to the height of the right subtree, and then adding 1 to account for the node itself. This can be expressed as:

Diameter = 1 + Left Subtree Height + Right Subtree Height

Approach:

1. Start by initializing a global variable diameter to keep track of the maximum diameter encountered during the traversal. This variable will be updated at each node as the tree is traversed.
2. Create a recursive function called calculateHeight that calculates the height of each node. For each node, compute the height of its left and right subtrees, and use these values to determine the current diameter by summing the heights. Continuously update the diameter variable with the maximum value encountered during this process.
3. Begin traversing the tree from the root node, utilizing the calculateHeight function to compute and update the maximum diameter at each node. Once the traversal is complete, return the value stored in diameter as the final result.

Code:

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // Global variable to store the diameter
    int diameter = 0;

    // Function to calculate the height of a subtree
    int calculateHeight(TreeNode* node) {
        if (node == nullptr) {
            return 0;
        }

        // Recursively calculate the height of left and right subtrees
        int leftHeight = calculateHeight(node->left);
        int rightHeight = calculateHeight(node->right);

        // Update the global diameter if the current diameter is larger
        diameter = std::max(diameter, leftHeight + rightHeight);

        // Return the height of the current subtree
        return 1 + std::max(leftHeight, rightHeight);
    }

    // Function to find the diameter of a binary tree
    int diameterOfBinaryTree(TreeNode* root) {
        // Reset the diameter for the new tree
        diameter = 0;

        // Start the recursive traversal from the root
        calculateHeight(root);

        // Return the maximum diameter found during traversal
        return diameter;
    }
};

int main() {
    // Create a binary tree for testing
    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);

    // Create a Solution object and find the diameter
    Solution sol;
    std::cout << "Diameter of the binary tree is: " << sol.diameterOfBinaryTree(root) << std::endl;

    // Clean up the tree to avoid memory leaks
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N^2) In this approach, for each node, we calculate the height of its left and right subtrees, which takes O(N) time. Since this calculation is done for each of the N nodes in the tree, the total time complexity is O(N * N) = O(N^2)
• Space Complexity: O(H) The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the tree, H. Thus, the space complexity is O(H).

2️⃣ Optimal Approach

Intuition:

The previous method for calculating the diameter of a binary tree can be refined by eliminating the repetitive calculations of subtree heights. In the earlier approach, the heights of the left and right subtrees are computed multiple times for each node, leading to inefficient and redundant computations. A more efficient strategy is to calculate these heights in a bottom-up fashion using a Postorder traversal. This technique enables the validation of balance conditions and the computation of the diameter simultaneously during the traversal.

Approach:

1. Start by initializing a variable diameter to keep track of the maximum diameter of the tree. Then, create a helper function named height that accepts a node and a reference to the diameter variable.
2. For the base case, if the node is null, return 0. In the recursive function, compute the heights of the left and right subtrees for each node. Determine the current diameter by adding these subtree heights together and then adding 1 to account for the node itself. Update the global diameter variable with the maximum value encountered so far.
3. Once the entire tree has been traversed, return the maximum diameter recorded during the traversal as the final result.

Code:

// Definition for a binary tree node.
  struct TreeNode {
      int data;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
  };
 

class Solution {
public:
    // Function to find the diameter of a binary tree
    int diameterOfBinaryTree(TreeNode* root) {
        // Initialize the variable to store the diameter of the tree
        int diameter = 0;
        
        // Call the height function to traverse the tree and calculate diameter
        height(root, diameter);
        
        // Return the calculated diameter
        return diameter;
    }

private:
    // Function to calculate the height of the tree and update the diameter
    int height(TreeNode* node, int& diameter) {
        // Base case: If the node is null, return 0 indicating an empty tree height
        if (!node) {
            return 0;
        }

        // Recursively calculate the height of left and right subtrees
        int lh = height(node->left, diameter);
        int rh = height(node->right, diameter);

        // Update the diameter with the maximum of current diameter 
        diameter = max(diameter, lh + rh);

        // Return the height of the current node's subtree
        return 1 + max(lh, rh);
    }
};

int main() {
    // Example usage: Create a tree and find its diameter
    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 solution;
    int result = solution.diameterOfBinaryTree(root);
    cout << "Diameter of the binary tree is: " << result << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N) In the optimized approach, each node is visited once, and its height is calculated during the post-order traversal.
• Space Complexity: O(H) The space complexity is determined by the maximum depth of the recursion stack, which corresponds to the height of the tree, H.