CareerCup

This is very similar to the tree diameter problem: at any node the longest path may belong to a subtree or go through the node itself if it's white. Just track recursively the longest path of each subtree and the length of white-path ending at current node:

struct Tree
{
   enum Color { White, Black };
   typedef std::list<Tree *> Children;

   Color color;
   Children children;
};

// curr - the lenght of path ending at root
// max  - the length of longest path in this subtree
void longestPath(Tree * root, size_t & curr, size_t & max)
{
   curr = 0;
   max  = 0;

   if (!root)
      return;

   size_t maxc[2] = {0, 0};

   for (Children::const_iterator i = root->children.begin(); i != root->children.end(); ++i)
   {
      size_t c = 0;
      size_t m = 0;

      longestPath(*i, c, m);

      if (max < m)
         max = m;

      if (maxc[0] < m) {
         maxc[1] = maxc[0];
         maxc[0] = m;
      } else if (maxc[1] < m) {
         maxc[1] = m;
      }
   }

   if (root->color == White) {
      curr = 1 + maxc[0];

      if (max < 1 + maxc[0] + maxc[1])
         max = 1 + maxc[0] + maxc[1];
   }
}

size_t logestPath(Tree * root)
{
   size_t curr = 0;
   size_t max  = 0;

   longestPath(root, curr, max);
   return max;
}

This code will do find the path in one scan of the tree:
Please correct me if I have got something wrong.

struct state
{
	int maxPathLength;
	int amIinMaxPAth;	// 0==> No , 1==> I am in the path, 2==> I am the center of the path
	int currPathLength;
	int maxWithoutCenter;
};


struct state findLongestWhitePath(struct treeDef *p1)
{
	struct state leftStatus,rightStatus;
	struct state curState;
	curState.maxPathLength=curState.amIinMaxPAth=curState.currPathLength=0;
	if(p1 != NULL)
	{
		leftStatus=findLongestWhitePath(p1->left);
	
		rightStatus=findLongestWhitePath(p1->right);
		
		if(p1-> left == NULL && p1->right == NULL)
		{
			// I am a leaf node..
			if(p1->color == 'w' || p1->color == 'W')
			{
					curState.maxPathLength = curState.currPathLength=1;
					curState.amIinMaxPAth=1;
			}
			else
			{
					curState.maxPathLength = curState.currPathLength=0;
					curState.amIinMaxPAth=0;
			}
		return 	curState;
		}
		else
		{
			//This is black color
			if(p1-> color == 'B' || p1-> color =='b')
			{
				curState.maxPathLength=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
				curState.amIinMaxPAth=0;
				curState.currPathLength=0;
			}
			else // This is white color
			{
				//This belong to maxPath
				//1. If both of my child belong to max path
				if(leftStatus.amIinMaxPAth == 2 && rightStatus.amIinMaxPAth == 2)
				{
					curState.amIinMaxPAth=2;// I am at the center...
					curState.maxPathLength=leftStatus.maxWithoutCenter + rightStatus.maxWithoutCenter +1;
					curState.currPathLength=curState.maxPathLength;
					curState.maxWithoutCenter=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
				}
				else if(leftStatus.amIinMaxPAth == 2)
				{
					curState.amIinMaxPAth=0;
					curState.currPathLength=leftStatus.maxWithoutCenter +1;
					curState.maxPathLength=leftStatus.maxPathLength;
					if(curState.currPathLength > curState.maxPathLength)
					{
						curState.amIinMaxPAth=1;
						curState.maxPathLength=curState.currPathLength;
					}
				}
				else if (rightStatus.amIinMaxPAth == 2)
				{
					curState.amIinMaxPAth=0;
					curState.currPathLength=rightStatus.maxWithoutCenter +1;
					curState.maxPathLength=rightStatus.maxPathLength;
					if(curState.currPathLength > curState.maxPathLength)
					{
						curState.amIinMaxPAth=1;
						curState.maxPathLength=curState.currPathLength;
					}
				}
				else if(leftStatus.amIinMaxPAth == 1 && rightStatus.amIinMaxPAth == 1)
				{
					curState.amIinMaxPAth=2;// I am at the center...
					curState.maxPathLength=leftStatus.maxPathLength + rightStatus.maxPathLength +1;
					curState.currPathLength=curState.maxPathLength;
					curState.maxWithoutCenter=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
				} 
					//2. If any one of my child belong to maxPath
				else if( leftStatus.amIinMaxPAth == 1 )
				{
					curState.amIinMaxPAth=1;
					curState.maxPathLength=leftStatus.maxPathLength +1;
					curState.currPathLength=curState.maxPathLength;
					
				}
				else if(rightStatus.amIinMaxPAth == 1)
				{
					curState.amIinMaxPAth=1;
					curState.maxPathLength=rightStatus.maxPathLength +1;
					curState.currPathLength=curState.maxPathLength;
				}
				else // None of my childs are in maxPath
				{
					curState.amIinMaxPAth=0;
					curState.maxPathLength=max(leftStatus.maxPathLength,rightStatus.maxPathLength);
					curState.currPathLength=1+max(leftStatus.currPathLength,rightStatus.currPathLength);
					if(curState.currPathLength > curState.maxPathLength)
					{
						curState.maxPathLength=curState.currPathLength;
						curState.amIinMaxPAth=1;
					}
				}
			//It does not belong to maxPath
			}
				
		}
		
	}
	return 	curState;
}

int main()
{
	struct state length;	
	createBSTree();
	length=findLongestWhitePath(root);	
	printf("\nLongest White Path Length Is:%d\n",length.maxPathLength);
	return 0;	
}

int whitenodes(node root, int max)
{
if(root == null)
return 0;
if(root.value == white)
{
int newmax = max(1+ whitenodes(root.right, max), 1+whitenodes(root.left,max));
if(newmax>max)
max = newmax;
}
else
newmax = 0;
return newmax;
}

answer will be in max (not newmax)

int search(node,flag)
{
val=val1=val2=0;
if(node.color=Black )
{
if(node->left != NULL)
val1=search(node->left,0);
if(node->right != NULL)
val2=search(node->right,0);
return max(val1,val2);
}
else
{
val=1;
if(node->left != NULL)
{
val+=search(node->left,1);
val1=search(node->left,0);
}
if(node->right != NULL)
{
val+=search(node->right,1);
val2=search(node->right,0);
}
if(flag=1)
{
return max(val1,val2);
}
else return max(val,val1,val2);
}
}

the final value in global variable max is the answer.

static int max = Integer.MIN_VALUE;

 private static int fn(Node root) {

        if (root == null) return 0;
        int l = fn(root.left);
        int r = fn(root.right);
        if (root.data % 2 == 1) {
            int innerMax = l > r ? l : r;
            if (innerMax > max) {
                max = innerMax;
                return 0;
            }
        }
        return l + r + 1;
    }

int Longesthpath(root, MaxPathInSubtree, MaxPathEndingAtNode) {
MaxPathInSubtree = 0;
MaxPathEndingAtNode = 0;

if(root == null)
{
return 0;
}

LongethPath(root->left, MaxPathInSubtree1, MaxPathEndingAtNode1);
LongethPath(root->left, MaxPathInSubtree2, MaxPathEndingAtNode2);

if(x is white)
{
MaxPathEndingAtNode = 1 + max( MaxPathEndingAtNode1, MaxPathEndingAtNode2);
}
else
{
MaxPathEndingAtNode = 0;
}

MaxPathInSubtree = max (MaxPathEndingAtNode, MaxPathInSubtree1, MaxPathInSubtree2);

if(max_so_far < MaxPathInSubtree)
max_so_far = MaxPathInSubtree;
}

Modification of well known graph problem of finding longest path in a directed acyclic graph (DAG):
- topologically sort the tree using dfs and throw away all black nodes
- perform linear backwards scan on the resulting list calculating max path of white nodes starting at particular vertex. Two nodes are considered adjacent in the list if they are adjacent in the original tree