## Facebook Interview Question

Android Engineers**Country:**United States

**Interview Type:**Phone Interview

```
// This function returns overall maximum path sum in 'res'
// And returns max path sum going through root.
int findMaxUtil(Node* root, int &res)
{
//Base Case
if (root == NULL)
return 0;
// l and r store maximum path sum going through left and
// right child of root respectively
int l = findMaxUtil(root->left,res);
int r = findMaxUtil(root->right,res);
// Max path for parent call of root. This path must
// include at-most one child of root
int max_single = max(max(l, r) + root->data, root->data);
// Max Top represents the sum when the Node under
// consideration is the root of the maxsum path and no
// ancestors of root are there in max sum path
int max_top = max(max_single, l + r + root->data);
res = max(res, max_top); // Store the Maximum Result.
return max_single;
}
// Returns maximum path sum in tree with given root
int findMaxSum(Node *root)
{
// Initialize result
int res = INT_MIN;
// Compute and return result
findMaxUtil(root, res);
return res;
}
```

public static int getMaxPathSum(Node root) {

int suml = 0;

int sumr =0;

if (root.l == null && root.r == null) return root.val;

if (root.l != null ) {

suml = suml + root.val + getMaxPathSum(root.l);

}

if (root.r != null ) {

sumr = sumr + root.val + getMaxPathSum(root.r);

}

return Math.max(suml, sumr);

}

```
public static int getMaxPathSum(Node root) {
int suml = 0;
int sumr =0;
if (root.l == null && root.r == null) return root.val;
if (root.l != null ) {
suml = suml + root.val + getMaxPathSum(root.l);
}
if (root.r != null ) {
sumr = sumr + root.val + getMaxPathSum(root.r);
}
return Math.max(suml, sumr);
```

}

```
function getMaxPathSum(Tree) {
const leftNode = Tree.left;
const rightNode = Tree.right;
if (leftNode === null && rightNode === null) {
return Tree.value;
}
const sumLeft = Tree.value + getMaxPathSum(leftNode);
const sumRight = Tree.value + getMaxPathSum(rightNode);
if (sumLeft >= sumRight) {
return sumLeft;
}
return sumRight;
}
```

Well, I think that you can have a path which doesn't necessarily go through the root...That means that we have to find the path between any two nodes which constitutes the maximum sum...The below code achieves that

```
def find_height_by_value(node):
if node is None:
return 0
return node.data + max(find_height_by_value(node.left), find_height_by_value(node.right))
def find_max_sum(node):
if node is None:
return 0
lheight = find_height_by_value(node.left)
rheight = find_height_by_value(node.right)
lmax = find_max_sum(node.left)
rmax = find_max_sum(node.right)
return max(max(lmax, rmax), node.data + lheight + rheight)
root = Node(4)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.right.right = Node(6)
print("MAXIUMUM SUM = ",find_max_sum(root))
```

The output for the above test case is 20...

```
def find_height_by_value(node):
if node is None:
return 0
return node.data + max(find_height_by_value(node.left), find_height_by_value(node.right))
def find_max_sum(node):
if node is None:
return 0
lheight = find_height_by_value(node.left)
rheight = find_height_by_value(node.right)
lmax = find_max_sum(node.left)
rmax = find_max_sum(node.right)
return max(max(lmax, rmax), node.data + lheight + rheight)
root = Node(4)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(2)
root.right.right = Node(6)
print("MAXIUMUM SUM = ",find_max_sum(root))
```

The path can be between any two nodes constituting the maximum sum...It doesn't necessarily has to pass through the root node.

```
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.res = float('-inf')
self.dfs(root)
return self.res
def dfs(self, node):
if not node: return 0
l = self.dfs(node.left)
if l < 0: l = 0
r = self.dfs(node.right)
if r < 0: r = 0
if l+r+node.val > self.res:
self.res = l+r+node.val
return node.val + max(l,r)
```

```
/*
Given a binary tree, where each node represents an integer,
find the max value of path sum.
*/
/*
Clarification:
Can I have negative values as nodes values? YES
Can I assume that all the numbers are integer? YES
Should the root be on the path? NO
Brute force: For every every node, I'll consider this nodes as the start node
and I'll try with the rest of the nodes as the finish node.
Time complexity is O(N*N)
Better solution is: For every node, has a value that is the max path that start
in that node and goes to the subtree.
Then, we can compare and merge this values to get the final answer.
*/
class BTree{
public:
long long value,sum;
BTree * left, * right;
BTree(long long _value, BTree * _left, BTree * _right){
value=_value;
left=_left;
right=_right;
sum=max({0LL,value,getSum(left)+value,getSum(right)+value});
}
static long long maxPath(BTree * tree){
if(!tree)return 0;
long long ans=max({tree->sum,maxPath(tree->left),maxPath(tree->right)});
ans=max(ans,tree->value+getSum(tree->left)+getSum(tree->right));
return ans;
}
static long long getSum(BTree * tree){
if(!tree)return 0;
return tree->sum;
}
};
int main() {FIN;
BTree f(2,NULL,NULL);
BTree g(1,NULL,NULL);
BTree c(3,&f,&g);
BTree d(4,NULL,NULL);
BTree e(5,NULL,NULL);
BTree b(3,&d,&e);
BTree a(2,&b,&c);
cout<<BTree::maxPath(&a)<<"\n";
}
```

```
/*
Given a binary tree, where each node represents an integer,
find the max value of path sum.
*/
/*
Clarification:
Can I have negative values as nodes values? YES
Can I assume that all the numbers are integer? YES
Should the root be on the path? NO
Brute force: For every every node, I'll consider this nodes as the start node
and I'll try with the rest of the nodes as the finish node.
Time complexity is O(N*N)
Better solution is: For every node, has a value that is the max path that start
in that node and goes to the subtree.
Then, we can compare and merge this values to get the final answer.
*/
class BTree{
public:
long long value,sum;
BTree * left, * right;
BTree(long long _value, BTree * _left, BTree * _right){
value=_value;
left=_left;
right=_right;
sum=max({0LL,value,getSum(left)+value,getSum(right)+value});
}
static long long maxPath(BTree * tree){
if(!tree)return 0;
long long ans=max({tree->sum,maxPath(tree->left),maxPath(tree->right)});
ans=max(ans,tree->value+getSum(tree->left)+getSum(tree->right));
return ans;
}
static long long getSum(BTree * tree){
if(!tree)return 0;
return tree->sum;
}
};
int main() {FIN;
BTree f(2,NULL,NULL);
BTree g(1,NULL,NULL);
BTree c(3,&f,&g);
BTree d(4,NULL,NULL);
BTree e(5,NULL,NULL);
BTree b(3,&d,&e);
BTree a(2,&b,&c);
cout<<BTree::maxPath(&a)<<"\n";
}
```

```
/*
Given a binary tree, where each node represents an integer,
find the max value of path sum.
*/
/*
Clarification:
Can I have negative values as nodes values? YES
Can I assume that all the numbers are integer? YES
Should the root be on the path? NO
Brute force: For every every node, I'll consider this nodes as the start node
and I'll try with the rest of the nodes as the finish node.
Time complexity is O(N*N)
Better solution is: For every node, has a value that is the max path that start
in that node and goes to the subtree.
Then, we can compare and merge this values to get the final answer.
*/
class BTree{
public:
long long value,sum;
BTree * left, * right;
BTree(long long _value, BTree * _left, BTree * _right){
value=_value;
left=_left;
right=_right;
sum=max({0LL,value,getSum(left)+value,getSum(right)+value});
}
static long long maxPath(BTree * tree){
if(!tree)return 0;
long long ans=max({tree->sum,maxPath(tree->left),maxPath(tree->right)});
ans=max(ans,tree->value+getSum(tree->left)+getSum(tree->right));
return ans;
}
static long long getSum(BTree * tree){
if(!tree)return 0;
return tree->sum;
}
};
```

```
/*
Given a binary tree, where each node represents an integer,
find the max value of path sum.
*/
/*
Clarification:
Can I have negative values as nodes values? YES
Can I assume that all the numbers are integer? YES
Should the root be on the path? NO
Brute force: For every every node, I'll consider this nodes as the start node
and I'll try with the rest of the nodes as the finish node.
Time complexity is O(N*N)
Better solution is: For every node, has a value that is the max path that start
in that node and goes to the subtree.
Then, we can compare and merge this values to get the final answer.
*/
class BTree{
public:
long long value,sum;
BTree * left, * right;
BTree(long long _value, BTree * _left, BTree * _right){
value=_value;
left=_left;
right=_right;
sum=max({0LL,value,getSum(left)+value,getSum(right)+value});
}
static long long maxPath(BTree * tree){
if(!tree)return 0;
long long ans=max({tree->sum,maxPath(tree->left),maxPath(tree->right)});
ans=max(ans,tree->value+getSum(tree->left)+getSum(tree->right));
return ans;
}
static long long getSum(BTree * tree){
if(!tree)return 0;
return tree->sum;
}
};
```

}

- Anonymous May 07, 2018