# 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).

• Very Nice and easy to understand solution!!

• Cool solution. Do add code in Java also.

• #### 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 approach. :)

• nice solution, easy to implement

• Nice solution. Keep going 👍

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

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