Program 23RD in C++ VERSION 1

PROBLEM STATEMENT :

What is the diameter of a tree?

SOLUTION :

#include <iostream.h>

#include <cstdio>

using namespace std;

int flag=1;

struct node

{

int data;

node* left;

node* right;

};

int max(int a, int b)

{

return (a > b ? a : b);

}

int height(node* n)

{

if(n == 0)

{

return 0;

}

else

{

return 1+max(height(n->left),height(n->right));

}

}

node* node(int val)

{

struct node* m=(struct node*)malloc(sizeof(struct node));

m->data=val;

m->left=NULL;

m->right=NULL;

return m;

}

int diameter(struct node* n)

{

if(flag == 1 && n->left == 0)

{

n=n->right;

return diameter(n);

}

else if (flag == 1 && n->right == 0)

{

n=n->left;

return diameter(n);

}

else

{

flag = 0 ;

}

if(n == 0)

{

return 0;

}

int lh = height(n->left);

int rh = height(n->right);

int ld = diameter(n->left);

int rd = diameter(n->right);

return(max(lh+rh+1,max(ld,rd)));

}

int main()

{

struct node* root;

root = node(0);

root->left = node(1);

root->right = node(7);

root->right->right = node(4);

//root->right->left = node(7);

root->right->right->right = node(3);

//root->right->right->right->left = node(8);

root->right->right->right->right = node(2);

cout<<diameter(root);

}