Tree Longest Path: O(n) C code

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:

1. 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).
2. O(n) - We visit each node only once. So time complexity O(n).

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