#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int value) {
data = value;
left = NULL;
right = NULL;
}
};
int diameterOpt(Node* root, int* height) {
int lh=0,rh=0;
int ldiameter=0;
int rdiameter=0;
if(root == NULL)
{
*height =0;
return 0;
}
ldiameter = diameterOpt(root->left,&lh);
rdiameter = diameterOpt(root->right,&rh);
*height = max(lh,rh)+1;
return max(lh+rh+1,max(ldiameter,rdiameter));
}
// Driver Code
int main() {
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
int height = 0;
cout << diameterOpt(root, &height) << endl;
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3QgTm9kZSB7CiAgICBpbnQgZGF0YTsKICAgIE5vZGUgKmxlZnQsICpyaWdodDsKICAgIE5vZGUoaW50IHZhbHVlKSB7CiAgICAgICAgZGF0YSA9IHZhbHVlOwogICAgICAgIGxlZnQgPSBOVUxMOwogICAgICAgIHJpZ2h0ID0gTlVMTDsKICAgIH0KfTsKCmludCBkaWFtZXRlck9wdChOb2RlKiByb290LCBpbnQqIGhlaWdodCkgewogIAogIGludCBsaD0wLHJoPTA7CiAgICAKICBpbnQgbGRpYW1ldGVyPTA7CiAgaW50IHJkaWFtZXRlcj0wOwogIAogIGlmKHJvb3QgPT0gTlVMTCkKICB7CiAgCSpoZWlnaHQgPTA7CiAgCXJldHVybiAwOwogIH0KICAgIAogICAgbGRpYW1ldGVyID0gZGlhbWV0ZXJPcHQocm9vdC0+bGVmdCwmbGgpOwogICAgcmRpYW1ldGVyID0gZGlhbWV0ZXJPcHQocm9vdC0+cmlnaHQsJnJoKTsKICAgIAogICAgKmhlaWdodCA9IG1heChsaCxyaCkrMTsKICAgIAogICAgCiAgICByZXR1cm4gbWF4KGxoK3JoKzEsbWF4KGxkaWFtZXRlcixyZGlhbWV0ZXIpKTsKfQoKLy8gRHJpdmVyIENvZGUKaW50IG1haW4oKSB7CgogICAgLyogQ29uc3RydWN0ZWQgYmluYXJ5IHRyZWUgaXMKICAgICAgICAgICAgMQogICAgICAgICAgIC8gXAogICAgICAgICAgMiAgIDMKICAgICAgICAgLyBcCiAgICAgICAgNCAgIDUKICAgICovCiAgICBOb2RlKiByb290ID0gbmV3IE5vZGUoMSk7CiAgICByb290LT5sZWZ0ID0gbmV3IE5vZGUoMik7CiAgICByb290LT5yaWdodCA9IG5ldyBOb2RlKDMpOwogICAgcm9vdC0+bGVmdC0+bGVmdCA9IG5ldyBOb2RlKDQpOwogICAgcm9vdC0+bGVmdC0+cmlnaHQgPSBuZXcgTm9kZSg1KTsKCiAgICBpbnQgaGVpZ2h0ID0gMDsKICAKICAgIGNvdXQgPDwgZGlhbWV0ZXJPcHQocm9vdCwgJmhlaWdodCkgPDwgZW5kbDsKCiAgICByZXR1cm4gMDsKfQ==