CareerCup

int dia(NODE* TREE, int *diameter)
{

if (tree == NULL)
return 0;

int left= 1+dia(tree->left,diameter);
int right = 1+dia(tree->left,diameter);

if ( (left+right) > *diameter )
*diameter= left+right;

if (left > right)
return left;
else
return right;


}

a level order traversal .. keeping track of the length of the queue and then the maximum length of the queue.... anything better than this?

not correct

1. What kind of tree it is.
2. Please provide proper definition of Diameter of a tree.

for each node, treat it as a subtree, record/compute its depth. ------ O(N)

traverse tree, for each node, find two children with largest depth, add depths up, plus 2. Always record the greater result during the traversal. ------ O(N)

well well well, can the question-poster please make use of his brain and "search" to make sure you are not creating duplicating posts. this question has been asked hell of times in this forum. please don't fool others by re-posting questions.
if you still find yourself sitting on the couch doing nothing , you can use this link

http://tinyurl.com/yj2rvdr

enjoy and good luck you.

let me know if iam wrong in thinking of diameter as something like this :
find out the height of the left subtree of the root
find out the height of the right subtree of the root ,

now add the heights + 1 should give me the diameter of the tree .. any suggestions or comments , abt this pls ..

main()
{
.....
.....
// diameter of the binary tree is :
j = height(root->left);
k = height(root->right);
diameter = j+k;
printf("the max diameter of the binary tree is %d",diameter);
getch();
}
int height(struct node *p)
{
int k = 1,l =1;
if(p==NULL)
return 0;
else
{
k = 1+height(p->left);
l = 1 + height(p->right);
if(k>l) return k;
else return l;
}
}

no you can not say like this as diameter is the largest distance b/w two nodes..
so conditions are
1) one node in left sub tree,one in right sub tree
2) both in left sub tree
3) both in right sub tree
can be done in O(N) in the following way...
(int, int) findDiameterInner(Node n)
{
if (n == null) return (0, 0)

(a, b) = findDiameterInner(n.leftChild);
(c, d) = findDiameterInner(n.rightChild);
depth = max(a, c) + 1;
dia = max(b, d, a + c);
return (depth, dia);
}

int findDiameter(Node root)
{
(depth, dia) = findDiameterInner(root);
return dia;
}

gnu: What is the data structure for the types you defined in your code: (int, int), (a,b), (c,d), (depth, dia)? Are these simply arrays or maybe something else. Please clarify if possible. Thanks.

int getDiameterCore(node *root, int *diameter)
{
	if (root == NULL)
		return -1;
	int h1 = getDiameterCore(root->left,diameter);
	int h2 = getDiameterCore(root->right,diameter);
	if (h1+h2+2 > *diameter)
		*diameter = h1+h2+2;
	return 1+max(h1,h2);
}

int getDiameter(node *root)
{
	int diameter = 0;
	getDiameterCore(root,&diameter);
	return diameter;
}

if height is a parameter of the node, then a O(height) = O(logN) can be achieved. here is the algorithm:

1. find the diameter at the node, as the sum of left->height + right->height + 1
2. follow the path from node to the node at max depth node.

mathematically, it can be argued that the max depth node at the root of the tree will remain the max node for every subtree, and thus will be a part of the diameter of the tree, whether or not the current node lies on the diameter.

The following URL gives detailed explination:

h**p://crackinterviewtoday.wordpress.com/2010/03/11/diameter-of-a-binary-tree/