CareerCup

Tested for all edge cases -

public int sumOfAllGreater(TreeNode root, int i){
		if(root == null){
			return i;
		}
		else if(root.leftChild == null && root.rightChild == null){
			root.data += i;
			return root.data;
		}
		
		int tmp = sumOfAllGreater(root.rightChild, i);
		root.data += tmp;
		tmp = sumOfAllGreater(root.leftChild, root.data);
		return tmp;
	}

Should call sumOfAllGreater(bst.root, 0) initially..

This means that each node will contain its data + sum of all node's data in right subtree.
node->data = node->data + (sum of all nodes in right subtree).
Reverse Inorder would do the work for us.

Code:
int sum = 0; //global variable
sum_max (node *root)
{
if (root == NULL)
return;

sum_max (root->right);
sum = sum + root->data;
root->data = sum;
sum_max (root->left);
}

1. Postorder travarsal.
     2. currnode --> data += prevNode-->data

}

int fun(struct node *right)
{
    if(!root->right)
         return root->data;
    root->data+=fun(root->right);
    return (root->data +fun(root->left));
}

If we have performed the requisite algorithm (rollUp) on the right subtree of a node, and now we need to perform that on the current node, we can just consider the value of the right node.

But the issue here is that the right node had ignored it's left subtree for getting it's value(because at any node, all the nodes in the right subtree have value greater than it.)

But this neglected left subtree of the current node's right node is important for calculating the value of current node.

So what we can do is.. we can try to remember the left subtree's sum, at any node of the tree, while doing recursion.

Do a Reverse Inorder. First Right subtree, then root, then Left.

(Postorder is not right as root node will get sum of all its children!)

Probably something like this (note: not tested)

void Summer(const Tree *t) {
    int so_far = 0;
    SummerInternal(t, so_far);
}
 
void SummerInternal(const Tree *t, int &so_far /*input, output*/) {
    if (t == NULL) return;
    
    Summer(t->right, so_far);
    
    int tmp = t->value;
    t->value += so_far;
    so_far += tmp;
    
    Summer(t->left, so_far);
}

I guess it is the "flipped" in-order traversal, which is different from post-order.

// "func" returns ("a" + sum),
// sum is equal to the sum of all the original elements in BST rooted at "r".
int func(Node r, int a) {
    if (r == null) return a;
    r.data += func(r.right, a);
    return func(r.left, r.data);
}

if a node is left child of its parent ,it will be having its right subtree sum and its parent and parents right subtree also

int inorder(struct node* root,int sum)
{
static int sum1=0;
if(root != NULL)
{
inorder(root->right,sum1);
sum1+=root->data;
root->data= sum1;
printf("%d,",root->data);
inorder(root->left,sum1);

return root->data;
}

else
return 0;

}

int inorder(struct node* root,int sum)
{
static int sum1=0;
if(root != NULL)
{
inorder(root->right,sum1);
sum1+=root->data;
root->data= sum1;
printf("%d,",root->data);
inorder(root->left,sum1);

return root->data;
}

else
return 0;

}

addRight(NODEPTR node)
{
   if(node==NULL) return 0;
   if(node->right==NULL & node->left==NULL) //leaf node
        return node->info;
   node->info=node->info+addRight(node->right);
   return node->info+addRight(node->left);
}

Every time the function should return the sum and this sum must be passed to every recursive call. We are thereby passing the maximum value of all the nodes to call and reverse inorder traversal does the trick.

int Func(Node* root,int sum){
int rsum,lsum;
if(root==NULL)return sum;

rsum = func(root->right,sum);
root->data= rsum+root->data;
rsum=root->data;
printf("\t%d",root->data);
lsum=func(root->left,root->data);
if(rsum>lsum)sum = rsum;
else sum =lsum;
return sum;
}

Hi Friends , can you please explain me how it differs weather i use reverse inorder traversal or post order traversal as long as right traversal is before the current node evaluaiton. What i mean is


public void Traverser(Object node){

if(node.right != null) Traverser(node.right);

node.value+ = node.right.value;

if(node.left !=null ) Traverse(node.left);


}


Or

public void Traverser(Object node){

if(node.right != null) Traverser(node.right);

if(node.left !=null ) Traverse(node.left);

node.value+ = node.right.value;

}




Or

public void Traverser(Object node){


if(node.left !=null ) Traverse(node.left);

if(node.right != null) Traverser(node.right);

node.value+ = node.right.value;



}


all 3 functions should return me the same result is it not ? what am i missing ? please help

sorry i could not understand your que.. greater than all nodes means value wise greater all node or.. anything else.can you please tell more detail.

sumGreaterNodes( Node node , int parentValue){
if(node==null){
return 0;
}
int sumNodesRight = sumGreaterNodes(node.right, parentValue);
int temp = node.value;
node.value += (sumNodesRight + parentValue);
int sumNodesLeft = sumGreaterNodes(node.left, node.value);
return temp + sumNodesRight + sumNodesLeft;
}

this tree is then no longer a BST.. Should that be done as well ?

O(n^2)

Algorithm

Go to each node and calculate right subtree sum. Top Down approach. 2 Recursive calls. Java code follows:

private static void goToEachNodeRecCall(TreeEntry node) {
		
		if (node == null)
			return ;
		
		node.data = node.data + calculateSums(node.right);
		
		goToEachNodeRecCall(node.left);
		goToEachNodeRecCall(node.right);
	}
	
	private static int calculateSums(TreeEntry node) {
		
		if (node == null)
			return 0;
		
		int sum = node.data;
		
		int left = calculateSums(node.left);
		int right = calculateSums(node.right);
		
		sum = sum + left + right;
		
		return sum;
	}

What happens if the predecessor has the same value as the current node? Do you count it as a sum or replica? I think what may be best is if in addition to returning sum from recursive call, one also returns a predecessor having greater key.

//Process right subtree and then left subtree

int sum_BST(Node* iter)
{
if(iter==NULL) return 0;
iter->data = iter->data + sum_inorder(iter->rc);
return sum_inorder(iter->lc) + iter->data;
}

int sum_BST(Node* iter)
{
if(iter==NULL) return 0;
iter->data = iter->data + sum_inorder(iter->rc);
return sum_inorder(iter->lc) + iter->data;
}

int SumofRightTree(Tree *tree, bool isRight)
{
if(tree != NULL)
{
SumofRightTree(tree->left, false);
tree->data = tree->data + SumofRightTree(tree->right, true);
return tree->data;
}
else
return 0;

}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {30,10,5,20,50,40,60};
Tree *root= NULL;

for(int i=0;i<7; i++)
root = CreateTree(root, arr[i]);

SumofRightTree(root, true);
return 0;
}

int SumofRightTree(Tree *tree, bool isRight)
{
if(tree != NULL)
{
SumofRightTree(tree->left, false);
tree->data = tree->data + SumofRightTree(tree->right, true);
return tree->data;
}
else
return 0;

}
int _tmain(int argc, _TCHAR* argv[])
{
int arr[] = {30,10,5,20,50,40,60};
Tree *root= NULL;

for(int i=0;i<7; i++)
root = CreateTree(root, arr[i]);

SumofRightTree(root, true);
return 0;
}

int sum(NODE *T)
{
if (T==NULL)return 0;

sum(T->left); //dont use return val
int temp = T->data;
T->data = temp + sum(T->right);
return(temp);

}

Please suggest mistake in the code if any.

int convert(TREE root)
{
    int sumval = 0;
	if(root==NULL)return 0;
	convert(root->left);
	convert(root->right);
	if(root->left!=NULL || root->right!=NULL)
	{       //        cout<<"\n poitning to "<<root->info;
	sum(root->left,root->info,&sumval); //important cz though it is a BST initially still it is possible that the left child becomes greater than root intdelf
	sum(root->right,root->info,&sumval);
    root->info += sumval;
	//cout<<root->info;
	sumval = 0;
   }
}
int sum(TREE root,int val,int *sumval)
{
	//int sumval = 0;
	if(root==NULL) return 0;
	if(root->info > val)
	{
    //cout<<"\n Found greater = "<<root->info<<" than "<<val; 
     (*sumval)+=root->info;
     //cout<<"\n sumval = "<<*sumval;
     sum(root->left,val,sumval);
     sum(root->right,val,sumval);
     
     }

}

int transform(struct Node* root, int sum) {
  if (!root) return sum;

  root->data += transform(root->right, sum);
  return transform(root->left, root->data);
}

As most of the people said...keep adding the right children to the curr node while doing rev inorder.Only gotcha was returning sum back when we hit null.This is because, when we hit null, we are essentially returning from right hand side back to parent node always.Even in the case , when we return from left side of child node back to childs parent.

private static int fn2(Node root,int sum) {
        if(root==null) return sum;
        int right=fn2(root.right,sum);
        root.data=root.data+right;
        return fn2(root.left,root.data);
    }

sum(tree*root)
{
static int sum ;
if(!root) return ;
sum(root->right) ;
root.data=sum+root.data ;
sum=root.data ;
sum(root.left) ;