CareerCup

I think the interviewer asked to find the tree diameter. Tree diameter is the max distance between any two nodes in the tree. This can be found in O(n) time.

This is tree diameter problem.

Idea is max distance will be in left subtree or in right subtree or it will pass through root.
We can do it recursively.

int height(struct node* root) {
       if(root == NULL) {
             return 0;
       }

       int leftHeight = height(root->left);
       int rightHeight = height(root->right);
       if(leftHeight > rightHeight) {
              return leftHeight + 1;
       } else {
              return rightHeight + 1;
       }
}

int diameter(struct node* root) {
       if(root == NULL) {
              return 0;
       }
       int lHeight = height(root->left);
       int rHeight = height(root->right);

       int lDiameter = diameter(root->left);
       int rDiameter = diameter(root->right);

      return max(lHeight + rHeight + 1, max(lDiameter, rDiameter));
}

Assuming the binary tree has distinct values and we are given two key between which distance is to be calculated..

int find(node *t,int k,stack s)
{
	if (t->val == k)
		return 1;
	else if (t->l == null && t->r==null)
		return 0;
	else
	{
		int x;
		if (t->l!=null)
		{
			x=find(t->l,k,s);
			if (x>0)
			{
				s.push(t);
				return x+1;
			}
			x=find(t->r,k,s);
			if (x>0)
			{
				s.push(t);
				return x+1;
			}
		}
	}
}

The find function finds the given key and its length and pushes the path onto the stack. The find function is used for both keys. The stack is compared from top to find the common ancestor and twice its distance is subtracted from the sum of two keys to get the distance between them.

find common ancestor and return common ancestor to node A + common ancestor to node B distance

Find the deepest node on each side of the root. That should be the longest possible path between two nodes. Please let me know if im missing something.

Solution would be:

Run Postorder on binary tree...
take a static variable...
for each node :
if it is leaf node return 0 + 1(for branch connecting to parent)
else maximum of {left tree value, right tree value} + 1
(if either of child tree is not present take it as 0)......

at each node calculate current_max = left tree value + right tree value
if this is bigger than our static variable update our static varaible = current_max....

At end of the process our static variable will contain maximum distance between any of two nodes in our binary tree... :)

It is a question of finding maxDepth in a tree.

Do a tree walk while keeping track of the current path using a list, by appending the current node to the list when starting a new recursive call, and popping it when returning.
During the tree walk, look for for two nodes, and when each of them is found, copy the current path and store it for later.
At the end of the tree walk, copmpare the two paths node by node, to find the last common ancesotr. The ditance would be the sum of the rest of the nodes after the common ancestor in the two paths.

2logn

Find lowest common ancestor, then find distance from both

The answer to the above question would be to find the diameter of the given tree
Here's the code which works in O(n) :

int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;

/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 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 */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);

/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;

return max(lh + rh + 1, max(ldiameter, rdiameter));
}