Problem: The diameter or width of a tree is the number of nodes on the longest path between two leaves in the tree.
Example:
Example:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
diameter of left sub-tree,
diameter of right sub-tree)
Implementation:
int diameter(Node* node, int& height)
{
int lh = 0, rh = 0, ld = 0, rd = 0;
if(node == NULL)
{
height = 0;
return 0;
}
ld = diameter(node->left, lh);
rd = diameter(node->right, rh);
height = max(lh, rh) + 1;
return MAX(lh + rh + 1, ld, rd);
}
int diameter(Node* node, int& height)
{
int lh = 0, rh = 0, ld = 0, rd = 0;
if(node == NULL)
{
height = 0;
return 0;
}
ld = diameter(node->left, lh);
rd = diameter(node->right, rh);
height = max(lh, rh) + 1;
return MAX(lh + rh + 1, ld, rd);
}
Complexity: O(n)
The height in the code should be replaced with *height
ReplyDeleteThis comment has been removed by the author.
DeleteImprove your c++.
DeleteWhile I agree with your solution, I am having hard find figuring out why my solution might be incorrect. Appreciate your comments.
ReplyDeleteAs I see, we can maintain a max_sum variable and count the height of the left subtree (lh), height of right subtree (rh) and update the max_sum if lh + rh + 1 is its greater. We calculate this sum at each of the nodes in the tree.
From your solution, ultimately the diameters will be calculated based on heights of the left and right subtrees at some point of time in the code.