CareerCup

My idea:
1. Traverse the tree. For each node compute:
R - the path from the root (i.e. the sum of all nodes from the root to this node)
Q - the max path to a leaf
This me be done recursively in O(N) space and time.
2. Traverse the tree again maximizing Q of left subtree + Q of right subtree - R.

Here is a Java solution with O(n) time, O(logn) space

public int maxDiff(TreeNode root, RefInt maxDiff) {
 int depth = 0;

 if ( root != null) {
  int leftD = maxDiff(root.left, maxDiff);
  int rightD = maxDiff(root.right, maxDiff);
  int currDiff =lefD + rightD;
  depth = Math.max(leftD, rightD) + 1;
  
  if (maxDiff.myInt < currDiff)
   maxDiff.myInt = currDiff;
 }
 
 return depth;
}

public class RefInt{
 public int myInt;
}

A clarification: tree is a complete tree, i.e. either 0 or 2 children.

may the values be negative?

1. Calculate the height of tree(H) and number of leaf nodes(N).
2. Make a matrix of size NxH of the structure:

typedef struct
{
    int nodeData; /*actual node data*/
    int accNodeData; /* accumulated sum of node data till this node*/
}

and initialize it to MIN.
3. Traverse the tree and put fill the Matrix for each path.
4. Loop over the matrix and for each pair of row get MAX element(accumulated data)and accumulated sum till least common ancestor(can be easily found by actual data stored in matrix) and calculate the target value.Keep on updating for max of target value.
5. return max target value.
Space NxH
time O(N^2)

I think some better solution should also exist. Please let me know.

Added constraints :
1. modification of tree structure is not allowed.
2. it is possible in O(n) time.

Guys,
Isnt it standard "diameter of binary tree" problem?

Another way to view this problem is to return the nodes such that the sum from root to their lowest common ancestor (LCA) + sum from LCA to each of the nodes is maximum. Note that tree is binary and not necessarily BST. I would use depth first search:

int FindMaxSumNodes(TreeNode * root,
                    int pathSum,
                    int currMax,
                    TreeNode ** ppFirst, 
                    TreeNode ** ppSecond)
{
    if (root == NULL)
    {
        return 0;
    }

    int maxLeftSum = 0;
    TreeNode * pLeftMaxNode;
    if (root->Left != NULL)
    {
        maxLeftSum = FindMaxPathNode(root->Left, 
                                     &pLeftMaxNode);
    }
    
    int maxRightSum = 0;
    TreeNode * pRightMaxNode;
    if (root->Right != NULL)
    {
        maxRightSum = FindMaxPathNode(root->Right, 
                                      &pRightMaxNode);        
    }

    int maxSoFar = pathSum + root->Value + maxLeftSum + maxRightSum;
    maxSoFar = maxSoFar > currMax ? maxSoFar : currMax;

    int maxLeftInnerSum = 0;
    TreeNode * pLeftFirst;
    TreeNode * pLeftSecond;
    if (root->Left != NULL)
    {
        maxLeftInnerSum = FindMaxSumNodes(root->Left,
                                          pathSum + root->Value,
                                          maxSoFar,
                                          &pLeftFirst,
                                          &pLeftSecond);
    }

    int maxRightInnerSum = 0;
    TreeNode * pRightFirst;
    TreeNode * pRightSecond;
    if (root->Right != NULL)
    {
        maxRightInnerSum = FindMaxSumNodes(root->Right,
                                           pathSum + root->Value,
                                           maxSoFar,
                                           &pRightFirst,
                                           &pRightSecond);
        
    }

    int maxSoFar = Math::Max(maxSoFar,
                   Math::Max(maxLeftInnerSum, maxRightInnerSum));

    if (maxSoFar == maxLeftInnerSum)
    {
        *ppFirst = pLeftFirst;
        *ppSecond = pLeftSecond;        
    }
    else if (maxSoFar == maxRightInnerSum)
    {
        *ppFirst = pRightFirst;
        *ppSecond = pRightSecond;        
    }
    else if (maxSoFar == maxLeftSum + maxRightSum + root->Value)
    {
        *ppFirst = pLeftMaxNode;
        *ppSecond = pRightMaxNode;
    }

    return maxSoFar;
}

int FindMaxPathNode(TreeNode * root, TreeNode ** pChildNode)
{
    if ((root == NULL) || (pChildNode == NULL))
    {
         if (pChildNode != NULL)
         {
             *pChildNode = NULL;             
         }
         return 0;
    }

    if ((root->Left == NULL) || (root->Right == NULL))
    {
        *pChildNode = NULL;
        return 0;
    }

    int leftMax;
    TreeNode * pLeftNode;
    if (root->Left)
    {
        leftMax = FindMaxPathNode(root->Left, &pLeftNode);
    }

    int rightMax;
    TreeNode * pRightNode;
    if (root->Right)
    {
        rightMax = FindMaxPathNode(root->Right, &pRightNode);
    }

    *pChildNode = (leftMax > rightMax) ? pLeftNode : pRightNode;    
}

Steps:
1) For each of the non-leaf node , find the height of max left sub tree and max right sub tree and collect the nodes for which these hieghts are found in some global variable
2) While doing step 1 , for non-root non leaf nodes , find the sum of heights - distance they are from root and then do the comparison.
3) update the Hieght value and nodes details as per the comaprison result.
4) Once all the nodes are traversed , the nodes will hold the two required nodes value and the height will hold the distance: F(X,Y).

None of your algo is correct except tulley but its high in time and space complexity.
for below tree the output should be node 4 and 5 and the target value will be 14

-1
     2       -2
   6   7   -3  -4  
node1=-1
node2=2
node3=-2
node4=6
node5=7
node6=-3
node7=-4

Hi All,
Please check this code
http ideone.com/YF9qi

Can we do better than this?

<pre lang="" line="1" title="CodeMonkey85265" class="run-this">typedef struct AuxData
{
//add leaves giving maxD
int maxH;
int maxD;
int fromRootD;
} AuxData;

#define MAX( a, b ) ( ((a) > (b)) ? (a) : (b) )

void maxSumTwoLeaf(Node *node, AuxData &auxData,int *fromRootD)
{
(*fromRootD) += node->data; //distance from root

if (!node->left && !node->right)
{
auxData.maxD = auxData.maxH = node->data;
(*fromRootD) -= node->data;
return ;
}


AuxData auxData_l;
maxSumTwoLeaf(node->left, auxData_l, fromRootD);
AuxData auxData_r;
maxSumTwoLeaf(node->right,auxData_r, fromRootD);

auxData.maxH = MAX(auxData_l.maxH,auxData_r.maxH)+node->data;


auxData.maxD = (*fromRootD)+ auxData_l.maxH + auxData_r.maxH + node->data;
auxData.maxD = MAX(auxData.maxD,MAX(auxData_l.maxD,auxData_r.maxD));


(*fromRootD) -= node->data; //decrease when returning back


return ;


}</pre><pre title="CodeMonkey85265" input="yes">
</pre>

#include"queue"
#include <hash_map>
#include <iostream>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;
using namespace stdext;

const int MaxNum=100;

typedef struct treenode
{
int treeindex;
int value;
int pleft, pright, parent;
vector<int> node_to_leaf;
int root_to_node;

}TreeNode;
TreeNode nodearray[MaxNum];

void FillSumArray(int nodeindex,int presum,int NodeNum)
{

TreeNode& cnode=nodearray[nodeindex];
//compute root to node
cnode.root_to_node=cnode.value+presum;

if(cnode.pleft>0)
FillSumArray(cnode.pleft,cnode.root_to_node,NodeNum);
if(cnode.pright>0)
FillSumArray(cnode.pright,cnode.root_to_node,NodeNum);
//compute node to path
if(cnode.pleft>0&&cnode.pright>0)
{
for(int i=0;i<NodeNum;i++)
{
int leftvalue=nodearray[cnode.pleft].node_to_leaf[i];
int rightvalue=nodearray[cnode.pright].node_to_leaf[i];
cnode.node_to_leaf[i]=cnode.value+(leftvalue>rightvalue?leftvalue:rightvalue);
}
}
else if (cnode.pleft<0&&cnode.pright<0)
{
cnode.node_to_leaf[nodeindex]=cnode.value;
}
else if(cnode.pleft>0)
{
for(int i=0;i<NodeNum;i++)
{
int leftvalue=nodearray[cnode.pleft].node_to_leaf[i];
cnode.node_to_leaf[i]=cnode.value+leftvalue;
}
}
else if(cnode.pright>0)
{
for(int i=0;i<NodeNum;i++)
{
int rightvalue=nodearray[cnode.pright].node_to_leaf[i];
cnode.node_to_leaf[i]=cnode.value+rightvalue;
}
}
return;
}

bool compare(int a,int b)
{
return b<a;
}

int main(){

freopen("in.txt", "r", stdin);

int index,pleft,pright, value;
int count=0;
while(scanf("%d %d %d %d\n",&index,&pleft,&pright,&value)!=EOF)
{
nodearray[index].pleft=pleft;
if(pleft>0)
nodearray[pleft].parent=index;
nodearray[index].pright=pright;
if(pright>0)
nodearray[pright].parent=index;
nodearray[index].value=value;

count++;
}
for(int k=0;k<count;k++)
{
nodearray[index].node_to_leaf.resize(MaxNum);
for(int i=0;i<MaxNum;i++)
{
nodearray[index].node_to_leaf[i]=-1;
}
}

FillSumArray(0,0,count);

for(int i=0;i<count;i++)
{
TreeNode& cnode=nodearray[i];
sort(cnode.node_to_leaf.begin(),cnode.node_to_leaf.end(),compare);
;
int k=0;
}


return 0;
}

Please verify. Did not test this code.

Algo with complexity O(log n):

- Recurse down to the leaves and up. At each step, pass up the two max-sum paths (+ the current node value), and the corresponding leaf nodes.
- At each step, the problem gets broken down thus: T(m) = 2T(m/2) + O(1). Thus O(log n) overall.

struct node{ int value; node *left; node *right; );

void maxPathPair(node *root, node *&firstLeaf, node *&secondLeaf, int &maxPathSum, int &secondMaxPathSum)
{
   if (root == NULL)
   {
      firstLeaf = secondLeaf = NULL;
      maxPathSum = secondMaxPathSum = -1;
   }

   node *p[4];
   int sum[4];

   maxPathPair(root->left, p[0], p[1], sum[0], sum[1]);
   maxPathPair(root->right, p[2], p[3], sum[2], sum[3]);
   
   int max = -1;
   int imax = -1;
   for (int i = 0; i < 4; i++)
   {
      if (p[i] && sum[i] > max)
      {
         max = sum[i];
         imax = i;
      }
   }

   if (max == -1)
   {
       firstLeaf = root;
       secondLeaf = NULL;
       maxPathSum = root->value;
       secondMaxPathSum = -1;
       return;
   }

   firstLeaf = p[imax];
   maxPathSum = max + root->value;

   sum[imax] = -1;
   max = -1;
   imax = -1;
   for (int i = 0; i < 4; i++)
   {
      if (p[i] && sum[i] > max)
      {
         max = sum[i];
         imax = i;
      }
   }

   if (max == -1)
   {
       secondLeaf = NULL;
       secondMaxPathSum = -1;
   }
   else
   {
       secondLeaf = p[imax];
       secondMaxPathSum = max + root->value;
   }
}

int funcXY(node *n,int upsum,int& maxsum)
{
if(!n)
return;

int lsum=funcXY(n->left,upsum+n->data, maxsum);
int rsum=funcXY(n->right,upsum+n->data, maxsum);

maxhere=lsum+rsum+upsum+n->data;

if(maxhere>maxsum)
maxsum=maxhere;

return (n->data+max(lsum,rsum));

}

int maxsum=0;
funcXY(root,0,maxsum);

This problem is some kind like such a question: find the largest path in a binary tree. So this problem can be solved from top to down.

#include <iostream>
#include <boost/unordered_map.hpp>
using namespace boost;
using namespace std;
struct Node{
    int val;
    Node* left;
    Node* right;
};
unordered_map<Node*, int> l;
unordered_map<Node*, int> lh;

int max(int i, int j)
{
    return i > j ? i : j;
}
int max(int i, int j, int k)
{
    return max(max(i, j), k);
}

int largestheight(Node* T)
{
    if (T == NULL)
    {
        return 0;
    }
    if (lh.find(T) != lh.end())
    {
        return lh[T];
    }
    int largest = max(largestheight(T->left), largestheight(T->right)) + T->val;
    lh.insert(pair<Node*, int>(T, largest));
    return largest;
}

int largest(Node* T)
{
    if (T == NULL)
    {
        return 0;
    }
    if (l.find(T) != l.end())
    {
        return l[T];
    }
    int result = max(largest(T->left), largest(T->right), largestheight(T->left) + largestheight(T->right)) + T->val;
    l.insert(pair<Node*, int>(T, result));
    return result;
}

This can be solved in O(n) time and O(n) space

maintain cumulative sum in each node this requires O(n) space.
and each left and right subtree will return to its parent the maximum path from their parent to any leaf downwards.The value of F(X, Y) would then be the sum of value returned by left and right subtree minus the cumulative sum of the parent node.
In the end maxSum will store the max F(X, Y)
to print the solution we would need to traverse the tree again, but thats easy

here is the code::

int solve (node * root, int prevSum, int *maxSum) {
     if (root == null) { return 0; }
     
     root->cumulativeSum = root->data + prevSum;
     
     if (root->left == null && root->right == null) {                // if node is a leaf node
          return root->cumulativeSum;
     }
     
     leftValue = solve(root->left, root->cumulativeSum, &maxSum);
     rightValue = solve(root->right, root->cumulativeSum, &maxSum);
     
     // update the cumulativeSum which will now store the largest F(X, Y) of the leaf nodes having 
     // current node as LCA.
     root->cumulativeSum = leftValue + rightValue - 3 * root->cumulativeSum;
     if (root->cumulativeSum > *maxSum) {
          *maxSum = root->cumulativeSum;
     }
     // return the max of the parent to leaf path from the current node
     return max(leftValue, rightValue);
}

test

First, original formual can me changed from
F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y

to

F(x,y) = distanceFromCurrentNodeToRoot + maxDistanceToLeftLeaf + maxDistanceToRightLeaf

maxDistanceToLeaf is modified problem of finding max height of the tree. For each node keep track of distance to the root, find leaf with max distance to the right and left, and see if formula gives better result. If it does, you found your pair of leaves. In other words, tree is traversed from bottom up and every node is visited once. Here is quick and dirty code fragment:

private static Integer fx = null;
	private static Node[] pairOfNodes = null;
	
	public static Node maxLeaf(Node node, int sumFromRoot) {
		if (node == null) return null;
		/* keep track of sum from root to current node */
		sumFromRoot = sumFromRoot + node.val;
		
		/* find leaf with biggest sum on the left and right side */
		Node maxLeftLeaf = maxLeaf(node.left, sumFromRoot);
		Node maxRightLeaf = maxLeaf(node.right, sumFromRoot);
		
		Node nodeToReturn = null;
		/* if no leafs found, current node is a leaf itself */
		if (maxLeftLeaf == null && maxRightLeaf == null) {
			nodeToReturn = node;
	    /* right leaf exists but no left one */
		} else if (maxLeftLeaf == null) {
			nodeToReturn = maxRightLeaf;
		/* left leaf exists but no right one */	
		} else if (maxRightLeaf == null) {
			nodeToReturn = maxLeftLeaf;
		} else {
		/* right and left leafs found. Calculate Fx and if it is greate than current, update with new leafs */	
			Integer localFx = maxLeftLeaf.maxDistance + maxRightLeaf.maxDistance + sumFromRoot;
			if (localFx.compareTo(fx) > 0) {
				fx = localFx;
				pairOfNodes = new Node[]{maxLeftLeaf, maxRightLeaf};
			}
			/* return leaf that might result in max distance with some other leaf on the way back to the root  */
			nodeToReturn = maxLeftLeaf.maxDistance > maxRightLeaf.maxDistance ? maxLeftLeaf : maxRightLeaf;
		}
		
		/* increase distance of the node from bottom to current node */
		nodeToReturn.maxDistance += node.val;
		return nodeToReturn;
	}

	public static class Node { 
		Node left, right;
		int val;
		/* distance that is equal to sum of all values from bottom of the tree to current node */
		int maxDistance = 0;
	}