Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
class A {
static class Result {
int value;
Node node;
}
int sumOfTree(Node root, Result max) {
if (root == null) {
return 0;
}
int leftR = sumOfTree(root.left, max);
int rightR = sumOfTree(root.right, max);
int sum = leftR + rightR + root.value;
if (sum > max.value) {
max.value = sum;
max.node = root;
}
return sum;
}
public static void main(String[] args) {
Node root = ...; //create a tree
Result max = new Result(Integer.MIN, root);
new A().sumOfTree(root, max);
max.value; //max value
max.node; //max node
}
}
and the function is always returning the sum calculated whether it is greater or smaller than the current max
Do post-order traversation(left-right-parent). During traversation save the parent bode with max sum (left sum + rigth sum). Time: O(N)
The question says to return the Node itself while most solutions are returning the sum of this Node, so I guess the question was probably edited. Here is my recursive version to returning the Node.
The recursive method does 2 things: (1) set the sum of current node and (2) return the largest-sum Node under the current node.
static Node largestSum(Node n) {
if(n == null)
return null;
Node leftLargest = largestSum(n.left);
Node rightLargest = largestSum(n.right);
n.sum += (n.left != null ? n.left.sum : 0);
n.sum += (n.right != null ? n.right.sum : 0);
Node largest = n;
if(n.left != null && leftLargest.sum > largest.sum)
largest = leftLargest;
if(n.right != null && rightLargest.sum > largest.sum)
largest = rightLargest;
return largest;
}
start summing up value from leaf to root and while summing these value keep track of node largest sum up value. and passing this value to parents node.
int Max (node *root)
{
static node tmp=NULL ;
static int check=INT_MIN
if(!root)
return 0;
if(root->left ==NULL && root->right==NULL)
return root->data;
int L=Max(root->left);
int R =Max(root->right);
if( (root->data + L +R) >check)
{
tmp=root; //store the node with max value;
}
return (root->data +L +R) ;
}
tmp node will have largest sum up value.
//tmp node can be pass as a reference node also
}
Scala version. Returns SearchResult with tree node and sum of its direct child values. Because it is binary tree there is no need to search on the left if the right node is present.
case class Tree[+T](value:T, left:Option[Tree[T]], right:Option[Tree[T]])
case class SearchResult(t:Tree[Int], sum:Int)
def zeroIfNone(t:Option[Tree[Int]]):Int = t match {
case None => 0
case Some(t)=>t.value
}
def findNodeWithBiggestSum(t:Option[Tree[Int]]):Option[SearchResult] = {
def _compare(t1:Option[SearchResult], t2:Option[SearchResult]):Option[SearchResult] = {
if (t1.isEmpty) return t2
if (t2.isEmpty) return t1
//Both not empty
if (t1.get.sum > t2.get.sum) t1 else t2
}
def _computeResult(t:Option[Tree[Int]]):Option[SearchResult] = t match {
case None=>None
case Some(tree)=>
val leftValue = zeroIfNone(tree.left)
val rightValue = zeroIfNone(tree.right)
Some(SearchResult(tree, leftValue + rightValue))
}
def _find(t:Option[Tree[Int]], soFar:Option[SearchResult]):Option[SearchResult] = t match {
case None=>soFar
case Some(t)=> t.right match {
case None => _compare(_computeResult(Some(t)), _find(t.left, soFar))
case Some(rightTree)=>
_compare(_computeResult(Some(t)), _find(t.right, soFar))
}
}
_find(t, None)
}
package SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class DFS {
BTNode r = new BTNode(null, null, 0, Integer.MIN_VALUE);
public static void main(String [] args){
BTNode a = new BTNode(null, null, 4, Integer.MIN_VALUE);
BTNode b = new BTNode(null, null, 5, Integer.MIN_VALUE);
BTNode c = new BTNode(null, null, -1, Integer.MIN_VALUE);
BTNode d = new BTNode(null, null, 7, Integer.MIN_VALUE);
BTNode e = new BTNode(c, d, 3, Integer.MIN_VALUE);
BTNode f = new BTNode(a, b, 2, Integer.MIN_VALUE);
BTNode g = new BTNode(e, f, 1, Integer.MIN_VALUE);
DFS dfs = new DFS();
dfs.sumUp(g);
System.out.print(dfs.DFS(g).value);
}
public int sumUp(BTNode n){
if (n.left == null && n.right == null)
return n.sumUp = n.value;
else if (n.left == null)
return n.sumUp = n.value + sumUp(n.right);
else if (n.right == null)
return n.sumUp = n.value + sumUp(n.left);
else return n.sumUp = n.value + + sumUp(n.left) + + sumUp(n.right);
}
public BTNode DFS(BTNode n){
if (n.left != null)
DFS(n.left);
if (n.right != null)
DFS(n.right);
if (n.sumUp > r.sumUp) r = n;
return r;
}
}
package SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class BTNode {
public BTNode left;
public BTNode right;
public int value;
public int sumUp;
public BTNode(BTNode l, BTNode r, int v, int s){
left = l;
right = r;
value = v;
sumUp = s;
}
}
package SubTreeLargestSumUp;
public class DFS {
BTNode r = new BTNode(null, null, 0, Integer.MIN_VALUE);
public static void main(String [] args){
BTNode a = new BTNode(null, null, 4, Integer.MIN_VALUE);
BTNode b = new BTNode(null, null, 5, Integer.MIN_VALUE);
BTNode c = new BTNode(null, null, -1, Integer.MIN_VALUE);
BTNode d = new BTNode(null, null, 7, Integer.MIN_VALUE);
BTNode e = new BTNode(c, d, 3, Integer.MIN_VALUE);
BTNode f = new BTNode(a, b, 2, Integer.MIN_VALUE);
BTNode g = new BTNode(e, f, 1, Integer.MIN_VALUE);
DFS dfs = new DFS();
dfs.sumUp(g);
System.out.print(dfs.DFS(g).value);
}
public int sumUp(BTNode n){
if (n.left == null && n.right == null)
return n.sumUp = n.value;
else if (n.left == null)
return n.sumUp = n.value + sumUp(n.right);
else if (n.right == null)
return n.sumUp = n.value + sumUp(n.left);
else return n.sumUp = n.value + + sumUp(n.left) + + sumUp(n.right);
}
public BTNode DFS(BTNode n){
if (n.left != null)
DFS(n.left);
if (n.right != null)
DFS(n.right);
if (n.sumUp > r.sumUp) r = n;
return r;
}
}
int largestvaluesum(struct node *root,struct node **maxvaluenode)
{int maxsum;
if(root==NULL)
return 0;
int lsum=largestvaluesum(root->left,maxvaluenode);
int rsum=largestvaluesum(root->right,maxvaluenode);
if(maxsum<=max(lsum,rsum)+root->data)
{maxsum=max(lsum,rsum)+root->data;
*maxvaluenode=root;
}
return maxsum;
}
This changes the data in a node to the recursive sum of its children's data.
NODE* max;
visited = NULL;
do
{
while( p != NULL )
stack.push(p);
p = p->left;
while( !stack.empty() )
{
temp = stack.top();
if( temp->right == NULL || temp->right == visited )
stack.pop();
temp->data += (temp->left)?temp->left->data:0;
temp->data += (temp->right)?temp->right->data:0;
if( max == NULL ) max = temp;
else if( max->data < temp->data ) max = temp;
visited = temp;
continue;
if( temp->right != NULL )
p = temp->right;
break;
}
}while( p != NULL || !stack.empty() );
int subTreeWithMaxSum(node *root)
{
if(!root)
return 0;
if(!root->left && !root->right)
return root->data;
int lSum = subTreeWithMaxSum(root->left);
int rSum = subTreeWithMaxSum(root->right);
return max(root->data, max(root->data+lSum+rSum, max(root->data+lSum, root->data+rSum)));
}
sorry this is wrong... i thought to return sub tree with max sum...
Its not possible to return node, because you need to maintain 2 values one with intermediate data which is the solution and one to return to next top level.... so at a time its not possible to return 2 values from a function
Please have a look
node * maxSumSubtree( node * head, int &sumSubTree, int &maxSumSubtree)
{
if(head == NULL)
{
sumSubTree = 0;
maxSumSubtree =0;
return NULL
}
int leftSumSubTree = 0;
int rightSumSubTree = 0;
int maxLeftSumSubTree = 0;
int maxRightSumSubTree = 0;
node *leftMaxSumSubtree = NULL;
node *rightMaxSumSubtree = NULL;
leftMaxSumSubtree = maxSumSubtree(head->left, leftSumSubTree, maxLeftSumSubTree);
rightMaxSumSubtree = maxSumSubtree(head->right, rightSumSubTree, maxRightSumSubTree);
sumSubTree = head->data + leftSumSubTree +rightSumSubTree;
if(sumSubTree => maxRightSumSubTree && sumSubTree => maxLeftSumSubTree)
{
maxSumSubtree = sumSubTree;
return head;
}
else if(maxRightSumSubTree >= sumSubTree && maxRightSumSubTree >= maxLeftSumSubTree)
{
maxSumSubtree = maxRightSumSubTree;
return rightMaxSumSubtree;
}
else
{
maxSumSubtree = maxLeftSumSubTree;
return leftMaxSumSubtree;
}
}
public static TreeNode FindMaxSubtree(TreeNode node,Hashtable<TreeNode,Integer> sum)
{
if(node == null)
return null;
TreeNode leftMaxNode = FindMaxSubtree(node.LeftChild, sum);
TreeNode rightMaxNode = FindMaxSubtree(node.RightChild, sum);
int nodeSum = node.Data + (node.LeftChild == null? 0 : sum.get(node.LeftChild))
+ (node.RightChild == null? 0 : sum.get(node.RightChild)) ;
sum.put(node, nodeSum);
TreeNode maxNode = node;
int max = nodeSum;
if(leftMaxNode != null && sum.get(leftMaxNode) > max)
{
maxNode = leftMaxNode;
max = sum.get(leftMaxNode);
}
if(rightMaxNode != null && sum.get(rightMaxNode) > max)
{
maxNode = rightMaxNode;
max = sum.get(rightMaxNode);
}
return maxNode;
}
struct node * func(struct node *ptr)
{
if(ptr==NULL)
return NULL;
else
{
struct node *le,*re;
le=(struct node *)func(ptr->left);
re=(struct node *)func(ptr->right);
if(le!=NULL&&re!=NULL)
ptr->info=le->info+re->info+ptr->info;
else if(re==NULL&&le==NULL)
ptr->info=ptr->info;
else if(le==NULL)
ptr->info=re->info+ptr->info;
else if(re==NULL)
ptr->info=le->info+ptr->info;
return ptr;
}
}
// Store temp maxSumNode and initialize it to root
// Also maintain an extra field sum in every Node apart from value and next
public Node largestSumNode( Node root ){
sumOfNode(maxSumNode = root);
return maxSumNode;
}
private int sumOfNode( Node node ){
if( node != null ){
node.sum = node.value + sumOfNode(node.left) + sumOfNode(node.right);
if( node.sum >= maxSumNode.sum )
maxSumNode = node;
return node.sum;
}
return 0;
}
struct maxSumAndNode{
int maxSum ;
struct node *maxNode ;
};
struct maxSumAndNode rootNodeWithLargestSumUpValue(struct node *node, int maximum, struct node *ret)
{
int tempSum ;
struct maxSumAndNode st1,st2;
if(node == NULL){
struct maxSumAndNode result;
result.maxSum = maximum ;
result.maxNode = ret;
return result;
}
else
{
if((tempSum = printSum(node) )> maximum)
{
maximum = tempSum ;
st1 = rootNodeWithLargestSumUpValue(node->left , maximum, node);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , node);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}
else
{
maximum = maximum ;
st1= rootNodeWithLargestSumUpValue(node->left , maximum, ret);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , ret);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}
}
}
struct maxSumAndNode{
int maxSum ;
struct node *maxNode ;
};
struct maxSumAndNode rootNodeWithLargestSumUpValue(struct node *node, int maximum, struct node *ret)
{
int tempSum ;
struct maxSumAndNode st1,st2;
if(node == NULL){
struct maxSumAndNode result;
result.maxSum = maximum ;
result.maxNode = ret;
return result;
}
else
{
if((tempSum = printSum(node) )> maximum)
{
maximum = tempSum ;
st1 = rootNodeWithLargestSumUpValue(node->left , maximum, node);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , node);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}
else
{
maximum = maximum ;
st1= rootNodeWithLargestSumUpValue(node->left , maximum, ret);
st2 = rootNodeWithLargestSumUpValue(node->right , maximum , ret);
if(st1.maxSum > st2.maxSum)
{
return st1;
}
else
{
return st2;
}
}
}
}
stTree* MaxSubtreeSum(stTree* pTree,int& MaxSum,stTree*& pMaxNode)
{
if(pTree == NULL)
return pMaxNode;
int TempSum = SubTreeSum(pTree);
if(TempSum > MaxSum)
{
MaxSum = TempSum;
pMaxNode = pTree;
}
MaxSubtreeSum(pTree->left,MaxSum,pMaxNode);
MaxSubtreeSum(pTree->right,MaxSum,pMaxNode);
return pMaxNode;
}
int SubTreeSum(stTree* pTree)
{
if(pTree == NULL)
return 0;
return (pTree->data + SubTreeSum(pTree->left) + SubTreeSum(pTree->right));
}
can we return node without modifying the node values of without using a separate sum function.. this code is returning correct node but am modifying every node's value with its sum-up value..
tree* LargestSumNode(tree *p, int l, int r)
{
static int max = 0;
static tree *max_node = NULL;
if(!p) return max_node;
if(!p->left && !p->right)
{
if(p->data > max)
{
max = p->data;
max_node = p;
}
}
LargestSumNode(p->left, l, r);
l = p->left ? p->left->data : 0;
LargestSumNode(p->right, l, r);
r = p->right ? p->right->data : 0;
if(p->data + l + r > max)
{
max = p->data + l + r;
max_node = p;
}
p->data = p->data + l + r;
return max_node;
}
TREE isMax(TREE root)
{
if(root==NULL)return 0;
static int maxsum = 0;
static TREE newroot = NULL;
int ls = sum(root->left);
int rs = sum(root->right);
if(ls + rs + root->info > maxsum)
{
maxsum = ls + rs + root->info;
newroot = root;
cout<<"\n New max sum = "<<maxsum;
cout<<"\n new root = "<<newroot->info;
}
isMax(root->left);
isMax(root->right);
return newroot;
}
int sum(TREE root)
{
if(root==NULL)
return 0;
else
return (sum(root->left) + root->info + sum(root->right));
}
- Dragon March 04, 2012