Solution by pooja_kamal


  • 6

    Approach #1 Brute Force [Accepted]

    Intuition

    The diameter of a tree is the maximum of these three:

    (i) The diameter of tree’s left subtree

    (ii) The diameter of tree’s right subtree and

    (iii) The longest path between leaves that goes through the root of the tree

    Algorithm

    1. Get the height of left and right sub-trees

      int left_height = height(root->left);

      int right_height = height(root->right);

    2. Get the diameter of left and right sub-trees

      int left_diameter = diameterOfBinaryTree(root->left);

      int right_diameter = diameterOfBinaryTree(root->right);

    3. Return max of following three

      return max(left_height + right_height, max(left_diameter, right_diameter));

    C++

    class Solution {
    public:
    
    /*  The function Compute the "height" of a tree. */
      int height(TreeNode* node){
       /* base case tree is empty */
       if(node == NULL)
           return 0;
       /* If tree is not empty then height = 1 + max of left
          height and right heights */
       return 1 + max(height(node->left), height(node->right));
      }
    
      int diameterOfBinaryTree(TreeNode* root) {
             /* base case where tree is empty */
       if (root == NULL)
         return 0;
    
      /* get the height of left and right sub-trees */
      int left_height = height(root->left);
      int right_height = height(root->right);
    
      /* get the diameter of left and right sub-trees */
      int left_diameter = diameterOfBinaryTree(root->left);
      int right_diameter = diameterOfBinaryTree(root->right);
    
      /* Return max of following three
       1) Diameter of left subtree
       2) Diameter of right subtree
       3) Height of left subtree + height of right subtree */
      return (max(left_height + right_height,
      max(left_diameter, right_diameter)));
    
        }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n^2).

      We are calling height function for each node explicitly , which takes O(n)
      for one node. So, for n nodes it will take O(n^2).

    • Space complexity: O(1)
      (if we ignore the recursion stack).


    Approach #2 Optimized Method [Accepted]

    Algorithm

    The above implementation can be optimized by calculating the height
    in the same recursion rather than calling a height() function separately.
    Time complexity – O(n)

    C++

    
    class Solution {
    public:
    
    // This function calculates the diameter of a tree
    int diameterOptimized(TreeNode *root, int* height)
    {
      /* left_height --> Height of left subtree
         right_height --> Height of right subtree */
      int left_height = 0, right_height = 0;
    
      /* left_diameter  --> diameter of left subtree
         right_diameter  --> Diameter of right subtree */
      int left_diameter = 0, right_diameter = 0;
    
      if(root == NULL)
      {
        *height = 0;
         return 0;
         /* diameter is also 0 */
      }
    
      /* Get the heights of left and right subtrees in lh and rh
        And store the returned values in ldiameter and ldiameter */
      left_diameter = diameterOptimized(root->left, &left_height);
      right_diameter = diameterOptimized(root->right, &right_height);
    
      /* Height of current node is max of heights of left and
         right subtrees plus 1*/
      *height = max(left_height, right_height) + 1;
    
      return max(left_height + right_height, max(left_diameter, right_diameter));
    }
    
    
    int diameterOfBinaryTree(TreeNode* root) {
       /* base case where tree is empty */
       if (root == NULL)
           return 0;
    
       int height = 0;
       int diameter = diameterOptimized(root, &height);
       return diameter;
    }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n).

      We are not calling height function explicitly from each node, so
      time complexity is O(n).

    • Space complexity : O(1)
      (if we ignore the recursion stack).


    Approach #3 Another Optimized Method [Accepted]

    (Easy to understand)

    Algorithm

    Diameter of a tree can be calculated by only using the height function,
    because the diameter of a tree is nothing but maximum value of
    (left_height + right_height + 1) for each node.
    So we need to calculate this value (left_height + right_height + 1) for each
    node and update the result. This solution is very easy to understand.
    Time complexity – O(n)

    C++

    class Solution {
    public:
    
     int height(TreeNode* root, int& ans){
        if (root == NULL)
            return 0;
    
        int left_height = height(root->left, ans);
    
        int right_height = height(root->right, ans);
    
        // update the answer, because diameter of a
        // tree is nothing but maximum value of
        // (left_height + right_height + 1) for each node
        ans = max(ans, left_height + right_height);
    
        return 1 + max(left_height, right_height);
     }
    
     int diameterOfBinaryTree(TreeNode* root) {
             /* base case where tree is empty */
       if (root == NULL)
            return 0;
        int ans = INT_MIN; // This will store the final answer
        int height_of_tree = height(root, ans);
        return ans;
      }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n).

      We are using only height function to calculate its diameter, so
      time complexity is O(n).

    • Space complexity : O(1)
      (if we ignore the recursion stack).


  • 0

    Very Nice and easy to understand solution!!


  • 0
    R

    Cool solution. Do add code in Java also.


  • 0
    C

    @pooja_kamal said in Solution by pooja_kamal:

    Approach #1 Brute Force [Accepted]

    Intuition

    The diameter of a tree is the maximum of these three:

    (i) The diameter of tree’s left subtree

    (ii) The diameter of tree’s right subtree and

    (iii) The longest path between leaves that goes through the root of the tree

    Algorithm

    1. Get the height of left and right sub-trees

      int left_height = height(root->left);

      int right_height = height(root->right);

    2. Get the diameter of left and right sub-trees

      int left_diameter = diameterOfBinaryTree(root->left);

      int right_diameter = diameterOfBinaryTree(root->right);

    3. Return max of following three

      return max(left_height + right_height, max(left_diameter, right_diameter));

    C++

    class Solution {
    public:
    
    /*  The function Compute the "height" of a tree. */
      int height(TreeNode* node){
       /* base case tree is empty */
       if(node == NULL)
           return 0;
       /* If tree is not empty then height = 1 + max of left
          height and right heights */
       return 1 + max(height(node->left), height(node->right));
      }
    
      int diameterOfBinaryTree(TreeNode* root) {
             /* base case where tree is empty */
       if (root == NULL)
         return 0;
    
      /* get the height of left and right sub-trees */
      int left_height = height(root->left);
      int right_height = height(root->right);
    
      /* get the diameter of left and right sub-trees */
      int left_diameter = diameterOfBinaryTree(root->left);
      int right_diameter = diameterOfBinaryTree(root->right);
    
      /* Return max of following three
       1) Diameter of left subtree
       2) Diameter of right subtree
       3) Height of left subtree + height of right subtree */
      return (max(left_height + right_height,
      max(left_diameter, right_diameter)));
    
        }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n^2).

      We are calling height function for each node explicitly , which takes O(n)
      for one node. So, for n nodes it will take O(n^2).

    • Space complexity: O(1)
      (if we ignore the recursion stack).


    Approach #2 Optimized Method [Accepted]

    Algorithm

    The above implementation can be optimized by calculating the height
    in the same recursion rather than calling a height() function separately.
    Time complexity – O(n)

    C++

    
    class Solution {
    public:
    
    // This function calculates the diameter of a tree
    int diameterOptimized(TreeNode *root, int* height)
    {
      /* left_height --> Height of left subtree
         right_height --> Height of right subtree */
      int left_height = 0, right_height = 0;
    
      /* left_diameter  --> diameter of left subtree
         right_diameter  --> Diameter of right subtree */
      int left_diameter = 0, right_diameter = 0;
    
      if(root == NULL)
      {
        *height = 0;
         return 0;
         /* diameter is also 0 */
      }
    
      /* Get the heights of left and right subtrees in lh and rh
        And store the returned values in ldiameter and ldiameter */
      left_diameter = diameterOptimized(root->left, &left_height);
      right_diameter = diameterOptimized(root->right, &right_height);
    
      /* Height of current node is max of heights of left and
         right subtrees plus 1*/
      *height = max(left_height, right_height) + 1;
    
      return max(left_height + right_height, max(left_diameter, right_diameter));
    }
    
    
    int diameterOfBinaryTree(TreeNode* root) {
       /* base case where tree is empty */
       if (root == NULL)
           return 0;
    
       int height = 0;
       int diameter = diameterOptimized(root, &height);
       return diameter;
    }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n).

      We are not calling height function explicitly from each node, so
      time complexity is O(n).

    • Space complexity : O(1)
      (if we ignore the recursion stack).


    Approach #3 Another Optimized Method [Accepted]

    (Easy to understand)

    Algorithm

    Diameter of a tree can be calculated by only using the height function,
    because the diameter of a tree is nothing but maximum value of
    (left_height + right_height + 1) for each node.
    So we need to calculate this value (left_height + right_height + 1) for each
    node and update the result. This solution is very easy to understand.
    Time complexity – O(n)

    C++

    class Solution {
    public:
    
     int height(TreeNode* root, int& ans){
        if (root == NULL)
            return 0;
    
        int left_height = height(root->left, ans);
    
        int right_height = height(root->right, ans);
    
        // update the answer, because diameter of a
        // tree is nothing but maximum value of
        // (left_height + right_height + 1) for each node
        ans = max(ans, left_height + right_height);
    
        return 1 + max(left_height, right_height);
     }
    
     int diameterOfBinaryTree(TreeNode* root) {
             /* base case where tree is empty */
       if (root == NULL)
            return 0;
        int ans = INT_MIN; // This will store the final answer
        int height_of_tree = height(root, ans);
        return ans;
      }
    
    };
    

    Complexity Analysis

    • Time complexity : O(n).

      We are using only height function to calculate its diameter, so
      time complexity is O(n).

    • Space complexity : O(1)
      (if we ignore the recursion stack).

    Nice and helpful explanation.


  • 0
    P

    nice approach. :)


  • 0
    K

    nice solution, easy to implement


  • 0
    D

    Nice solution. Keep going 👍


  • 0
    L

    Very nice...easy to understand, good job
    Thank you
    Pooja


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.