Directi Interview Question Developer Program Engineers
Country: India
Interview Type: Written Test
NAME is correct.. here is what it looks like:
int maxSumOfLeafpaths(node* root, int * maxSum){
if (root==NULL)
return -1;
if (root->right==NULL && root->left ==NULL)
return root->data;
int leftSum = maxSumOfLeafpaths(root->left, maxSum);
int rightSum = maxSumOfLeafpaths(root->right, maxSum);
int maxSumAtCurrLevel = MAX(leftSum,rightSum)+ root->data;
if (leftSum+rightSum+ root->data > *maxSum){
*maxSum = leftSum+rightSum+ root->data;
}
return maxSumAtCurrLevel;
}
int maxLeafSum(TreeNode* root, int ps) // ps -> pathSum from root to left;
{
if (root == NULL) return 0;
int lps (0), rps(0);
int lans = root->left ? maxLeafSum(root->left, lps) : INT_MIN;
int rans = root->right ? maxLeafSum(root->right, rps) : INT_MIN;
ps = t->left + max(lps, rps);
return max(t->left + lps + rps, max(lans, rans));
}
// algo has some bugs fixed now
int maxLeafSum(TreeNode* root, int& root_to_leaf_sum)
{
if (root == NULL) return INT_MIN;
if (root->left == NULL && root->right == NULL) {
ps = root->val;
return INT_MIN;
}
int left_root_to_leaf_sum(0), right_root_to_leaf_sum(0);
int lans = maxLeafSum(root->left, left_root_to_leaf_sum);
int rans = maxLeafSum(root->right, right_root_to_leaf_sum);
root_to_leaf_sum = root->val + max(left_root_to_leaf_sum, right_root_to_leaf_sum);
return max(lans, rans, root_to_leaf_sum);
);
}
Don't you think its a modification of diameter in a binary tree where you have to do the little modification, using the values of nodes.
Check this out:-
http: www geeksforgeeks.org diameter-of-a-binary-tree
where \ is replaced by space
Please share your thoughts
Let us consider a different problem:
Now this can easily be solved easy via a depth first search (or a recursive algorithm).
Now consider the problem we want to solve:
Now suppose that the path we seek passes through the root. This can now be composed of two(or less) legs (see definition earlier) corresponding to each subtree. Notice that both the legs must be the maximum for the corresponding subtree.
- __NAME__ December 15, 2012So we break down the problem as follows.
1) Try to recursively find the maximum leaf to leaf path in both subtrees (i.e. not passing through the root).
2) Find the maximum legs in each subtree and add up, and compare with what you got in 1.
Both 1 and 2 can be combined into one recursive solution.