Given a binary tree, find the length of the longest path between any two nodes in the tree. This path may or may not pass through the root.
Table of Contents
Sample Input:
Tree:
1
/ \
2 3
/ \
4 5
Expected Output:
3
In this example, the longest path between any two nodes in the binary tree is 3, which corresponds to the path: 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3.
Time and Space Complexity:
The time complexity of the algorithm is O(n), where ‘n’ is the number of nodes in the binary tree. We need to visit each node once to compute the diameter. The space complexity is O(h), where ‘h’ is the height of the binary tree. In the worst case, the recursion stack can grow to the height of the tree.
C++ solution:
#include <iostream>
#include <algorithm>
// Definition for a binary tree node.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int diameterOfBinaryTree(TreeNode* root, int& maxDiameter) {
// Base case: if the root is null, the diameter is 0
if (root == nullptr) {
return 0;
}
// Recursively calculate the height of the left and right subtrees
int leftHeight = diameterOfBinaryTree(root->left, maxDiameter);
int rightHeight = diameterOfBinaryTree(root->right, maxDiameter);
// Update the maximum diameter found so far
maxDiameter = std::max(maxDiameter, leftHeight + rightHeight);
// Return the height of the current subtree (adding 1 for the current node)
return std::max(leftHeight, rightHeight) + 1;
}
int diameterOfBinaryTree(TreeNode* root) {
int maxDiameter = 0;
diameterOfBinaryTree(root, maxDiameter);
return maxDiameter;
}
int main() {
// Construct the binary tree for the sample input
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);
// Find the diameter of the binary tree
int diameter = diameterOfBinaryTree(root);
std::cout << "The diameter of the binary tree is: " << diameter << std::endl;
// Don't forget to free the allocated memory
// ...
return 0;
}
The diameterOfBinaryTree function recursively calculates the diameter of the binary tree. It starts from the root node and computes the height of the left and right subtrees. Then it updates the maximum diameter found so far based on the sum of left and right subtree heights. Finally, it returns the height of the current subtree (adding 1 for the current node).
In the given example, the function will correctly find the diameter of the binary tree as 3, and the output will be 3.
As mentioned earlier, the time complexity is O(n) as we need to visit each node once, and the space complexity is O(h) due to the recursion stack, where ‘h’ is the height of the binary tree.