Binary Tree Diameter in C++ (Time Complexity: O(n))

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 a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-100 <= Node.val <= 100

Understanding the Problem

The core challenge of this problem is to find the longest path between any two nodes in a binary tree. This path does not necessarily pass through the root. The significance of this problem lies in its applications in network design, biology (e.g., finding the longest path in phylogenetic trees), and various other fields where tree structures are used.

Potential pitfalls include misunderstanding the definition of the diameter (it is the number of edges, not nodes) and not considering paths that do not pass through the root.

Approach

To solve this problem, we need to think about how to traverse the tree and calculate the longest path. A naive solution might involve checking all pairs of nodes, but this would be highly inefficient with a time complexity of O(n^2).

An optimized solution involves using a depth-first search (DFS) to calculate the height of each subtree and the diameter simultaneously. This approach ensures that we only traverse each node once, resulting in a time complexity of O(n).

Optimized Approach

1. Use a helper function to perform DFS on the tree.

2. For each node, calculate the height of its left and right subtrees.

3. Update the diameter if the sum of the heights of the left and right subtrees plus one (for the current node) is greater than the current diameter.

4. Return the height of the subtree rooted at the current node.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize a variable to keep track of the maximum diameter.
Define a recursive function that calculates the height of a subtree.
In the recursive function, for each node, calculate the height of the left and right subtrees.
Update the diameter if the current path through the node is longer than the previously recorded diameter.
Return the height of the subtree rooted at the current node.

Code Implementation

#include <iostream>
#include <algorithm>

using namespace std;

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

class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        int diameter = 0;
        // Helper function to calculate height and update diameter
        function height = [&](TreeNode* node) {
            if (!node) return 0;
            int leftHeight = height(node->left);
            int rightHeight = height(node->right);
            // Update the diameter
            diameter = max(diameter, leftHeight + rightHeight);
            // Return the height of the current node
            return 1 + max(leftHeight, rightHeight);
        };
        height(root);
        return diameter;
    }
};

int main() {
    // Example usage:
    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 sol;
    cout << "Diameter of the tree: " << sol.diameterOfBinaryTree(root) << endl;

    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Edge Cases

Potential edge cases include:

A tree with only one node (the diameter is 0).
A tree where all nodes are on one side (e.g., a linked list).
A balanced tree with multiple levels.

Each of these cases is handled by the algorithm as it correctly calculates the height and updates the diameter for each node.

Testing

To test the solution comprehensively, consider the following test cases:

A single-node tree.
A tree with nodes only on the left or right side.
A balanced tree with multiple levels.
A tree with negative and positive node values.

Using a testing framework like Google Test can help automate and validate these test cases.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller subproblems.
Think about how to traverse the data structure efficiently.
Use helper functions to keep the code clean and modular.
Practice similar problems to improve your understanding and skills.

Conclusion

In this blog post, we discussed how to find the diameter of a binary tree using an optimized approach with a time complexity of O(n). We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: