CareerCup

If I remember correctly, one algorithm is to find the deepest node of the tree say D1, then assuming that D1 is the root, find the deepest node again, say D2. D1 to D2 will be the longest path.

If your tree has both child/parent pointers, this should be O(n) time algorithm, where n is the number of nodes. (assuming the tree is connected).

cant u use depth first search (dfs)

cant u use depth first search (dfs)

cant u use depth first search (dfs)

We can have recursive function

int length(Node *root)
{
if(root == 0)
return 0;
int right= length(root->right);
int left= length(root->left);
if( left > right )
return 1+ left;
else
return 1+right;

}

We can have recursive function

int length(Node *root)
{
if(root == 0)
return 0;
int right= length(root->right);
int left= length(root->left);
if( left > right )
return 1+ left;
else
return 1+right;

}

I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.

Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.

Please let me know if you don't agree.

I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.

Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.

Please let me know if you don't agree.

I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.

Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.

Please let me know if you don't agree.

I think longest path is same as maximum depth except for the difference that path information need to provided like {A C E H I } constitutes a longest path.

Longest Path : Set of nodes in order, which will have maximum number of nodes.
Maximum depth : Numerical value which tells about the height of the tree.

Please let me know if you don't agree.

Try proving that they are the same and you will realize yourself.

Using a queue and not using recursion will be more clear.

tree_height(mynode *p)
{
if(p==NULL)return(-1);
h1=tree_height(p->left)+1;
h2=tree_height(p->right)+1;
return(max(h1,h2));
}


TESTED and WORKING

How about using a wrapper function around the function tree_height(mynode*p) which calls it for all the nodes as root one by one. The maximum length for a tree would be the one which gives us maximum depth. Though this looks to be really inefficient if the number of nodes in the tree is large, but it is a correct solution.

Path is different than height.

Assume that the tree data structure has an additional fields (int longestChildDepth). A node's longest path = sum of (node->left's, node->right's height, 1). The maximum of the sum is the longest path.

Path is different than height.

Assume that the tree data structure has an additional fields (int longestChildDepth). A node's longest path = sum of (node->left's, node->right's height, 1). The maximum of the sum is the longest path.

Path is different than height.

A node's longest path = sum of left childs height, right childs height and 1. The maximum of this number is the longest path.

Assuming Longest Path of the tree is the diameter of the tree, the distance from the the root to its leaf.

Start from an arbitrary node and run a Bread First Search. Note the last node visited. From this node, run a BFS again. The distance from this node to the last node visited is the diameter of the tree.

The question, just mentioned a tree, is it right to assume that the tree is a binary tree and not an 'n'nary tree?

The question, just mentioned a tree, is it right to assume that the tree is a binary tree and not just an 'n'nary tree?

The question, just mentioned a tree, is it right to assume that the tree is a binary tree and not just an n-nary tree?

The question, just mentioned a tree, is it right to assume that the tree is a binary tree and not just an n-nary tree?

length of the longest path is called tree diameter.
diameter = max of ( height_of_left_child + 2 + height_of_right_child, diameter(left_child), diameter(right_child))

It is the same as tree diameter.The following link might be helpful

http://www.cs.duke.edu/~ola/courses/cps100spr96/tree/trees.html

answer = dia of tree, my code[working] in CPP is posted below.
here "depth" and "dia" are passed as reference to collect the values, they are un-initialized.

void BST::getDiameter(Node *head, int& depth, int& dia)const throw() {
	if (head == NULL) {
		//to counter the addition of 1 for a leaf node
		//depth is set to -1..........
     	depth = -1;
		dia = 0;
		return ;
	}

	int lDia;
	int rDia;
	int lDepth;
	int rDepth;

	getDiameter(head->left, lDepth, lDia);
	getDiameter(head->right, rDepth, rDia);

	depth = (lDepth > rDepth ? lDepth : rDepth) + 1;
	//           (A)
	//          /   \
	//         (C)   (B)
	//                \
	//                 (D)
	// totalDepth(A) = Depth(A->left) + Depth(A->right) +2 = 0+1 +2 = 3
	// IND = Inter Node Distance
	int IND = lDepth + rDepth + 2;
	dia = (lDia > rDia ? (lDia>IND?lDia:IND) : (rDia>IND?rDia:IND) );
	cout << "depth at " << head->data << " is:" << depth << " and dia is " << dia << endl;
 	
}

int Diameter(node *start)
{
    if(start == NULL) return -1;
    int l = 1 + Diameter(start->left);
    int r = 1 + Diameter(start->right);
    if(maximum < l+r+1)
       maximum = l+r+1;
    cout << maximum<< endl;
    return max(l,r);
}

the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.

int Diameter(node *start)
{
    if(start == NULL) return -1;
    int l = 1 + Diameter(start->left);
    int r = 1 + Diameter(start->right);
    if(maximum < l+r+1)
       maximum = l+r+1;
    cout << maximum<< endl;
    return max(l,r);
}

the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.

int Diameter(node *start)
{
    if(start == NULL) return -1;
    int l = 1 + Diameter(start->left);
    int r = 1 + Diameter(start->right);
    if(maximum < l+r+1)
       maximum = l+r+1;
    cout << maximum<< endl;
    return max(l,r);
}

the value of maximum will be longest path length which is also the diameter of tree.
maximum is a global variable here.

int depth(node *start)
{
if(start == NULL) return 0;
if(start->left == NULL)
int l = depth(start->left);
else
int l = 1 + depth(start->left);
if (start->right == NULL)
int r = depth(start->right);
else
int r = 1 + depth(start->right);
if(diameter< l+r)
diameter = l+r;
cout << diameter<< endl;
return max(l,r);
}

int depth(node *start)
{
if(start == NULL) return 0;
if(start->left == NULL)
int l = depth(start->left);
else
int l = 1 + depth(start->left);
if (start->right == NULL)
int r = depth(start->right);
else
int r = 1 + depth(start->right);
if(diameter< l+r)
diameter = l+r;
cout << diameter<< endl;
return max(l,r);
}

void findDiameter( node root,int& diameter,int& depth)
{
if (root->NULL)
{
depth = 0;
diameter = 0;
return 0;
}

findDiameter( root->left,diameterleft,depthleft);
findDiameter( root->right,diameterright,depthright);
diameter = max( depthleft+depthright+2, diameterleft,diameterright);
depth = max(depthleft+1,depthright+1);
}

void findDiameter( node root,int& diameter,int& depth)
{
if (root->NULL)
{
depth = 0;
diameter = 0;
return 0;
}

findDiameter( root->left,diameterleft,depthleft);
findDiameter( root->right,diameterright,depthright);
diameter = max( depthleft+depthright+2, diameterleft,diameterright);
depth = max(depthleft+1,depthright+1);
}

Too much shit, very little corn.

int Dia(struct node * tree)
{
if (tree == 0)
return 0;

int lheight = height(tree->left);

int leftD = Dia(tree->left);
int rightD = Dia(tree->right);

return max(lheight + rheight + 1, max(leftD, rightD));
}

This looks pretty definitive to me:

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

I saw this link somewhere on careercup, can't find it now though. One thing the above doesn't do is, find the actual path; just the length. I suppose it would be easy to modify it though, to associate the node responsible, with each length, in a pair (or tuple, or custom struct) and return /that/ instead of just the length. I haven't actually tried it though.

... here; question id: 1767700

(It's not /quite/ a dup because that's asking only for the diameter, not the complete path.)

However, though the overall algorithm is right, I'm dubious that it's correct in some details.

find the height of each child node and go to the child with the largest height. return path when a null node has been reached.

int getHeight(Node *root){
   if (root == NULL) return 0;
   if (root->left == NULL && root->right == NULL) return 1;
   else return max(getHeight(root->left), getHeight(root->right)) + 1;
}

int maxLevel(Node *root){
   int h = getHeight(root);
   int maxLevel = 0; int maxCount = 0;
   for (int i = 1; i<=h; i++){
  GNU nano 1.2.5                     File: spiralOrder.cpp

      int l = getHeight(root->left);
      int r = getHeight(root->right);
      if (l > r) return maxFuncUtil(root->left, path);
      else return maxFuncUtil(root->right, path);
   }
   else {
      return path;
      /*
      for (unsigned i = 0; i < path.size(); i++){
         cout << path[i] << "\n";
      */
   }
}

void maxPathFunc(Node *root){
   vector <int> path;
   vector <int> maxPath;
   maxPath = maxFuncUtil(root, path);
   for (unsigned i = 0; i < maxPath.size(); i++){
      cout << maxPath[i] << " -> ";
   }
   cout << "\n" << "length: " << maxPath.size() << "\n";
}