## Longest path between any two nodes of a Binary Tree

## Amazon Interview (May 2012)

### Problem Statement

Find the length of longest path between any two leaf nodes of a binary tree. Actually leaf nodes are at maximum distance so its okay to say nodes as well as leaf nodes.### Solution 1:

// O(n*n) code

int longestPath(node *root){

if(root==NULL)

return 0;

int left_height=0, right_height=0;

int left_max=0, right_max=0;

left_height = height(root->left);

right_height = height(root->right);

left_max = diameter(root->left);

right_max = diameter(root->right);

int temp = max(left_max,right_max);

return max(temp, left_height+right_height);

}

int height(node* root)

{

if(root == NULL)

return 0;

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

}

### Solution 2:

// O(n) code

// In this code we take adv of pointer and calculate the height in same recursion rather than

// calling height separately as in Solution 1.

int longestPath(node *root, int *h) {int left_height=0, right_height=0;

int left_max=0, right_max=0;

if(root==NULL) {

*h=0;

return 0;

}

left_max=longestPath(root->left,&left_height);

right_max=longestPath(root->right,&right_height);

*h=max(left_height,right_height)+1;

int temp = max(left_max,right_max);

return max(temp, left_height+right_height);

}

If you have a different approach in mind, please share it in comments section for our readers.

### Time Complexity:

- O(n*n) - For each node (total n nodes) we calculate height which takes further O(n) time.

So total time complexity O(n*n). - O(n) - We visit each node only once. So time complexity O(n).

If you find this blog somewhat helpful, please give a +1.

how will you print the longest path ??

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteI think you are missing a +1 in

ReplyDeletereturn max(temp, left_height+right_height);

I think you are missing a +1 in

ReplyDeletereturn max(temp, left_height+right_height);

I think you are missing a +1 in

ReplyDeletereturn max(temp, left_height+right_height+1);