CareerCup

"http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html"

for each node in a tree,{
store (height of left sub tree+height of right sub tree)
and two childs which are the reason for these height (note: if one of the child is null then store node itself instead null)
}

for the node which has highest sum, retrive its two childs stored in above procedures.
those two nodes(childs) are situated at maximum distance.

I think that the solution would be:
1) Find the next leaf node of the tree. Build the path(string) to the leaf node by adding "0" if move to the left node and adding "1" if move to the right node. I.e. in the sample of the tree in the comment above the path to N9 node is "100"
2) Check the leaf nodes buffer. If there are no items there, add the current leaf node.
3) If there are the nodes in the leaf buffer, for each of them:
i=0
while(current leaf node path[i] == next buffer item[i])
i++
distance = current leaf node path.length - i + next buffer item.length - i;
if(distance > max) max = distance.
Example:
In the comment above the path to N9 node is "100", the path to N6 node is 11; increase i until the characters at i position are the same. i is 1 after this operation;
so the distance between these node is 3-1 + 2-1 = 3;

Don't know the exact solution but it should be something like that :-
1. The two nodes, which are farthest, must be a leaf.
2. Amongst the two leaves, one should be from from the left subtree of root and the other from the right subtree.

I would like to proceed this way - find the deepest leaf of left sub tree of root.
Do the same for right sub tree of root - i.e. deepest leaf
The two nodes are our answer

Take a look at the second comment. The link to cs.duke.edu. Understand that code and thats all you need.

This is similar to finding the diameter of a tree:
diameter = MAX(LDIAMETER , RDIAMETER , RHEIGHT+LHEIGHT+1);

This is a variation of finding the diameter. Here is the code for the same.

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

typedef struct treenode
{
	struct treenode *left;
	struct treenode *right;
	int val;
}node;

node *node1='\0', *node2='\0';
int max = INT_MIN;

int FindNodes(node *tree, int *height, node **dnode)
{
	int lh=0, rh=0, leftD=0, rightD=0;
	node *lnode='\0', *rnode='\0';
	if(tree=='\0')
	{
		*height=0;
		*dnode='\0';
		return 0;
	}
	leftD = FindNodes(tree->left, &lh, &lnode);
	rightD = FindNodes(tree->right, &rh, &rnode);

	int max1 = (leftD > rightD?leftD:rightD);
	*height = 1 + (lh>rh?lh:rh);
	int max2 = lh+rh+1;
	if(lnode=='\0'&&rnode=='\0')
		lnode = rnode = tree;
	if(lh>rh)
		*dnode=lnode;
	else
		*dnode=rnode;
	if(max<lh+rh)
	{
		node1=lnode;
		node2=rnode;
		max = lh+rh;
	}
	return max1>max2?max1:max2;
}

main()
{
	node *tree = '\0';
	//construct tree with atleast two nodes.
	int height = 0;
	node *dnode = '\0';
	int D = FindNodes(tree, &height, &dnode);
	printf("Diameter is:%d\n",D);
	printf("Distant Nodes: %d, %d\n", node1->val, node2->val);

}

Farthest is not very clear.       In below tree if we compare N7-N9 vs N7-N6 which pair is farthest?   
                     N1
                    /   \
                 N2    N3
                /       /\
            N4          N5 N6
          /\           /\
       N7 N8         N9 N10

Same as finding the diameter of a binary tree but in this case we have to return the nodes as well.

I think there should be some restrictions in this problem where the distance between two nodes is no repeat node.so my solution is :
0 : there is only one path between two nodes in a tree.
1: travel the tree and transform the tree to the mapping mtrix .
2: use floyed algorithm to compute the distance between any two nodes.
3: record the farthest distance.

Find Deepest leaf in the left subtree of root and the deepest leaf of the right subtree and add their distances from the root. This can be done in linear time.

guess this would work though i dint check completely

typedef struct pair{
 Node n1;
 Node n2;
 int n1_dist;
 int n2_dist;
}Result;

Result Farthest(Node n){
 if(n==NULL){
  Result *p=malloc(sizeof(Result));
  p->n1=NULL;
  p->n2=NULL;
  n1_dist=0;
  n2_dist=0;
  return p;
 }
 if(n->left==NULL){
  Result *p1=malloc(sizeof(Result));
  p1->n1=n;
  p1->n2=n;
  n1_dist=0;
  n2_dist=0;
 }
 else
  Result *p1=Farthest(n->left);
 else if(n->right==NULL){
  Result *p2=malloc(sizeof(Result));
  p2->n1=n;
  p2->n2=n;
  n1_dist=0;
  n2_dist=0;
 }
 else
  Result *p2=Farthest(n->right);

 Result *p3=malloc(sizeof(Result));

 if(p1->n1_dist>p1->n2_dist){
  p3->n1_dist=p1->n1_dist+1;
  p3->n1=p1->n1;
 }

 else{
  p3->n1_dist=p1->n2_dist+1;
  p3->n1=p1->n2;
 }

 if(p2->n1_dist>p2->n2_dist){
  p3->n2_dist=p2->n1_dist+1;
  p3->n2=p2->n1;
 }

 else{
  p3->n2_dist=p2->n2_dist+1;
  p3->n2=p2->n2;
 }

 if((p1->n1_dist + p1->n2_dist)>(p2->n1_dist + p2->n2_dist)){
  if((p1->n1_dist + p1->n2_dist)>(p3->n1_dist + p3->n2_dist))
   return p1;
  else
   return p3;
 }

 else if((p2->n1_dist + p2->n2_dist)>(p3->n1_dist + p3->n2_dist))
  return p2;

 return p3;
}

O(nlogn)

#include <iostream>
#include <algorithm>

using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int value, Node* left, Node* right) : value(value), left(left), right(right) {}
    Node(int value) : value(value), left(0), right(0) {}
    ~Node() {
        delete left, right;
    }
};

Node* n(const int& x, Node* left, Node* right) {
    return new Node(x, left, right);
}

Node* n(const int& x) {
    return new Node(x, 0, 0);
}

template<class T, class K> struct Tuple {
    T one;
    K other;

    Tuple(T one, K other) : one(one), other(other) {}
};

template<class T> struct LikeTuple : Tuple<T, T> {
    LikeTuple(T one, T other) : Tuple<T, T>(one, other) {}
};

typedef Tuple<Node*, int> Height;

Height height(Node* root, Node* parent) {
    if (root == 0) return Height(parent, 0);
    Height left_height = height(root->left, root);
    Height right_height = height(root->right, root);
    if (left_height.other > right_height.other) {
        left_height.other++;
        return left_height;
    } else {
        right_height.other++;
        return right_height;
    }
}

Height height(Node *root) {
    return height(root, 0);
}

typedef Tuple<LikeTuple<Node*>, int> FarthestNodes;

FarthestNodes farthest_nodes(Node* root) {
    if (root == 0) return FarthestNodes(LikeTuple<Node*>(0, 0), 0);
    FarthestNodes left_farthest = farthest_nodes(root->left);
    FarthestNodes right_farthest = farthest_nodes(root->right);
    Height l_height = height(root->left);
    Height r_height = height(root->right);
    int root_dia = l_height.other + r_height.other + 1;
    if (root_dia > left_farthest.other && root_dia > right_farthest.other)
        return FarthestNodes(LikeTuple<Node*>(l_height.one, r_height.one), root_dia);
    else if (left_farthest.other > right_farthest.other)
        return left_farthest;
    else
        return right_farthest;
}
    

int main(int argc, char** argv) {
    Node* root = n(10,
                   n(5,
                     n(2,
                       n(0,
                         n(-1),
                         n(2, n(1), 0)),
                       0),
                     n(7,
                       n(6),
                       n(9, n(8), 0))),
                   n(12,
                     n(11),
                     n(15,
                       n(13, 0, n(14)),
                       0)));
    FarthestNodes nodes = farthest_nodes(root);
    cout << "Farthest nodes are: " << nodes.one.one->value << " <-> " << nodes.one.other->value << " and distance between them is " << nodes.other << endl;
    delete root;
    return 0;
}

Sample Tree:

1

/      \

2          3

/    \

4      5

/        /

6       7

/       /

8      9

The nodes farthest from each other are 8 and 9, taking six hops to get there.

Generate the following list for each leaf node in the tree (how to get there from root):

8: left, left, left, left

9: left, right, left, left

3: right

To get the distance between two nodes, you compare their lists starting from the left and remove all the instructions before they begin to differ. Then just add the size of the lists.

Distance between 8 and 9 is 6:

8: left (remove), left (+1), left (+1), left (+1)

9: left (remove), right (+1), left (+1), left (+1)

Distance between 8 and 3 is 5:

8: left (+1), left (+1), left(+1), left (+1)

3: right (+1)

It should be obvious where to go from here.

we can start from a leaf node and do a DFS so that we can get the distance of each node from the leaf node find the maximum of those.

Brief approach to the solution is, here any way its clear that farthest nodes will be the leaf nodes. so first traverse the tree using any of the tree traversal and keep the leaf nodes in list.
Next step is for each leaf node, find the distance between other nodes in the leaf list and keep track of the max length.
To find the length between two nodes, use the approach of finding the lowest common anscetor(LCA) between these node and sum up the length to each node from the LCA.

Brief approach to the solution is, here any way its clear that farthest nodes will be the leaf nodes. so first traverse the tree using any of the tree traversal and keep the leaf nodes in list.
Next step is for each leaf node, find the distance between other nodes in the leaf list and keep track of the max length.
To find the length between two nodes, use the approach of finding the lowest common anscetor(LCA) between these node and sum up the length to each node from the LCA.

1.If root contains left and right child,diameter will be the max distance.
2.If root is having only one child,
a.get the max height from root
b.go to node which has left right child and get the diameter for this node.
max of a or b will be answer.

Its very simple, count the number of leaf nodes, say it n. Make a table n * n. For each pair of node find the Lowest Common Ancestor and store it into the table. You just need to populate half the table ( either upper triangular matrix or lower). For e.g a cell in the table will contain the following string (LCA, depth of 1st leaf node from LCA, depth of second leaf node from LCA).

Once this table is populated you can just initialize max to 0. Iterate over the table and check the sum of depth1 and depth2 for each cell and appropriately modify the max variable if you find the sum > max. the answer is the in the cell from where the final value of the max comes from.

Firstly, we try to find the max distance by doing traversal. For each node Ni, max distance is max(1+heightOf(left(Ni))+heightOf(right(Ni))), and the exact Ni node (say M) with left sub-tree height value and right sub-tree height which gets max distance can be recorded. Then we do traversal again starting from M and find the two leaf nodes.

Would these nodes be first and last in in-order traversal of the tree?

two ends of inorder traversal of tree

void findHeight(sTree * root, int* height,int max,sTree** node)
{
if(root == NULL)
return;
max++;
//*height = max > *height?max:*height;
if(max > *height)
{
*height = max;
*node = root;
}
findHeight(root->lChild,height,max,node);
findHeight(root->rChild,height,max,node);

}
void findDia(sTree *root,sTree ** end,sTree** toend)
{
int Lheight = 0;
int Rheight = 0;
findHeight(root->lChild,&Lheight,0,end); // find height of left node
findHeight(root->rChild,&Rheight,0,toend);//height of right node
printf("dia = %d",Lheight+Rheight);

}

int main()
{
// asumtion a tree is already present On complexcity
sTree *end,*toend;
findDia(root,&end,&toend);
}

do a prefix take last element, a postfix and the first element of this is what you need,,

You can reuse the diameter method, but instead of returning int, you could return a custom class, say,

class NodeM{ int len; Node n;

}
basically allowing you to keep in mind which node returned the max height on either side. Let your diameter method return NodeM[]. So you have both nodes between which you had max distance.
You can optimize the diameter, which is exponential in complexity by calling diameter on left and right children, before calling height function. Making the solution linear.

Do the level order traversal. Return 2 leaf nodes which are at min level & max level