2. Diameter of a BInary tree #

Created Thursday 06 February 2020

• See from BT visualization

two cases are possible:

1. Both extremum on different sides, height(root->left) + height(root->right).
2. Both on the the same side, max(diameter(root->left), diameter(root->right));

this is the same as max(diameter**(root->left),** max**(diameter(root->right),** height(root->left) + height(root->right)))

• This is having very bad TC, because we repeat the same work. We could have saved the data somewhere.
• So we better return a <diameter, height> pair.
• For NULL, height = 0, diameter(distance to itself is 0).

pair<int, int> diameterOfBinaryTreehelper(TreeNode* root)
{
	if(root==NULL)
	{
		pair<int, int> ret(0, 0);
		return ret;
	}
	pair<int, int> dhleft = diameterOfBinaryTreehelper(root->left);
	pair<int, int> dhright = diameterOfBinaryTreehelper(root->right);

	// check if max diameter is > h1 + h2
	// diameter = max(diameter1, diameter2, h1+h2)
	// height = max
	pair <int, int> ret;
	ret.first = max(dhleft.first, max(dhright.first, dhleft.second+dhright.second));// diameter
	ret.second = 1 + max(dhleft.second, dhright.second); // height, the usual height thing
	return ret;
}

 int diameterOfBinaryTree(TreeNode* root)
{
	return diameterOfBinaryTreehelper(root).first;
}

• LeetCode uses the same height terminology.

Height = 0 for NULL Height = 1 for leaf.