CareerCup

Simply do reverse inorder and keep on adding the sum and updating the node will do the job..

int nodeSum( BNode* root, int sum )
{

if( !root ) return sum;

sum = nodeSum( root->right, sum );

int tmp = root->data;

if( (sum) != 0 )
root->data = sum;

sum += tmp;

sum = nodeSum( root->left, sum );

return sum;

}

The trick is to update the value of the node by the recursive value returned by right subtree
and at the same time returning the total value of all nodes rooted at subtree as function return value.

int UpdateTree (Node n)
{
   if (n == null)
   {
      return 0;
   }

   int rightValue = UpdateTree(n->Right);
   int leftValue = UpdateTree(n->Left);

   this->Value += rightValue;      // Update the value of the node

   return (rightValue + n->Value + leftValue);    // Return the total values in the subtree
}

I guess from the given node in BST, there are two possible points where the value of the nodes are bigger than the given node:
1. the right child node and its children/tree
2. the parent node and the parent's right children where the the given node is a node located in the left tree of that parent node.

So here is the simple code to do so:

public void replace(Node node) {
           if (node == null) return;
           if (node.right != null) {
                 node.value = sum(node.right);
           }

            Node parent = node.parent;
            while (parent != null && node == parent.right) {
               //keep looping until it reaches a parent where the given node is located on the left sub tree
                node = node.parent;
                parent = node.parent;
            }

            if (parent != null) {
                   node.value += parent.value + sum(parent.right);
            }
     }

     private int sum(Node node) {
          if (node == null) return 0;
          return node.value + sum(node.left) + sum(node.right);
     }

yes reverse inorder will work for this problem.

Tricky Post order traversal.

int sumNodes(Tree *root,int currValue){
if(root!=null){
root->value=sumNodes(root->right)+currValue;
sumNodes(root->left,currValue+root-Value);
return root->value;

}

}

void newBST(TreeNode node,int[] sum){
        if(node==null) return;
        newBST(node.right,sum);
        sum[0]=sum[0]+node.data;
        node.data=sum[0];
        newBST(node.left,sum);

}

Hello,
I have a little difficulty understanding expected output. For example, if a given BST is
30
20 40
10 25 33 46
37
so that in order traversal produces 10 20 25 30 33 37 40 46.
Now according to question, shouldn't 10 be replaced by sum of (20...46), 20 be replaced with (25... 46), & so on..? Or am I missing something?

/***************************************************************************
author :santosh
Description : Replace the node val with the sum of all the node values that are greater than
the current node value
Date/Time :Tuesday 08 May 2012 06:49:56 PM IST
****************************************************************************/
#include<iostream>
#include <cstdio>
#include<map>
#include<list>
using namespace std;

struct TNode
{
public:
int val;
TNode * lchild;
TNode * rchild;

TNode(int value=-1)
{
val = value;
lchild = NULL;
rchild = NULL;
}
};

class BSTree
{
public:
TNode * root;

void preorderTraverse(TNode * temp)
{
if(!temp)
return ;

cout<<temp->val<<" ";

preorderTraverse(temp->lchild);
preorderTraverse(temp->rchild);
}

BSTree() { root = NULL;}
BSTree(int value) {root = new TNode(value);}

void add(int value)
{
TNode ** temp = &root;
while( *temp)
{
if( value > (*temp)->val)
{
temp = &(*temp)->rchild;
}
else
{
temp = &(*temp)->lchild;
}

}

*temp = new TNode(value);
}

void update(TNode * root,TNode * parent)
{
cout<<__FUNCTION__<<endl;
if(!root) return;

TNode * modified_parent = parent;
if( ! parent)
{
modified_parent = root;
}
else
{
if( parent->val > root->val)
modified_parent = parent;
else
modified_parent = root;
}

cout<<" parent "<< modified_parent->val<<" val "<<root->val<<endl;

update(root->rchild, modified_parent);

cout<<root->val<<" is updated to ";
if(root->rchild )
{
TNode * temp = root->rchild;
while(temp->lchild)
temp = temp->lchild;

root->val += temp->val;

}
else if( parent && root->val < parent->val )
{

root->val += parent->val;
}
cout<<root->val<<endl;


update(root->lchild, root);

}

};

int main()
{
BSTree T(10);
T.add(15);
T.add(12);
T.add(11);
T.add(20);
T.add(13);
T.add(5);
T.add(7);
T.add(1);
T.add(6);

T.preorderTraverse(T.root);
cout<<endl;
T.update(T.root,NULL);
T.preorderTraverse(T.root);
cout<<endl;

return 0;
}

//plz run this code , your doubts will be cleared.

doesnt it means dat the current node value b replaced jst by the sum of the right child recursively??

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
int value;
struct node *left;
struct node *right;
} Tree;

Tree *newnode(int item)
{
Tree *temp = (Tree*)malloc(sizeof(Tree));
temp->value = item;
temp->left = NULL;
temp->right = NULL;

return(temp);
}

Tree *insert(Tree *root , int item)
{
if(root == NULL)
return newnode(item);

if(item <= root->value)
root->left = insert(root->left , item);
else
root->right = insert(root->right , item);

return(root);
}

int Value(Tree *root)
{
if(root == NULL)
return 0;

return(root->value);
}

// Tricky Post Order Traversal. Update the node value with sum of entire right subtree.
// To keep track of the sum of the left subtree use a variable left_value.
int Update(Tree *root)
{
int left_value;

if(root == NULL)
return(0);

root->value = Update(root->right) + root->value;
left_value = Update(root->left);

return(left_value + root->value);

}


void Print_Tree(Tree *root)
{
if(root == NULL)
return;

printf("%d-> ", root->value);
Print_Tree(root->left);
Print_Tree(root->right);

}

int main()
{
Tree *root = NULL;
root = insert(root , 4);
root = insert(root , 6);
root = insert(root , 2);
root = insert(root , 13);
root = insert(root , 11);
root = insert(root , 7);
root = insert(root , 9);
root = insert(root , 5);
root = insert(root , 14);

Print_Tree(root);
printf("\n");

Update(root);

Print_Tree(root);
printf("\n");

getch();
return 0;

}

int ReplaceVal(node* root, int leftSum)
{
if(root)
{
int rVal = 0;
int lVal = 0;
if(root->right)
rVal = ReplaceVal(root->right, leftSum);

if(root->left)
lVal = ReplaceVal(root->left, root->ch + rVal + leftSum);

int temp = root->ch;
root->ch = leftSum+rVal;

return temp+rVal+lVal;
}
}

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;
}

Take the inorder traversal, in to an arrayList
replace each element in the arrayList with the sum of other elements after current list
now again traverse the inorder tree, replacing the elements respectively


replaceElements(ArrayList arr,Node n){
if(n!=null){

replaceElements(arr,n.left);
n.value=arr.getNext();
replaceElements(arr.n.right);
}

}

void replaceNodeValueToSumOfGreaterNodeValue(struct node *node){
if(node == NULL){
return ;
}

else
{
node->data = node->data + printSum(node->right);
replaceNodeValueToSumOfGreaterNodeValue(node->left);
replaceNodeValueToSumOfGreaterNodeValue(node->right);
}
}

int printSum(struct node *node){
int sumOfNodes = 0;
if(node == NULL){
return 0;
}

else
{
sumOfNodes+=node->data+printSum(node->left) + printSum(node->right);
}
return sumOfNodes;
}

convertToSumTree(struct b_tree *d_node)
{
static int sum=0;
if (d_node==NULL)
return 0;
convertToSumTree(d_node->r_node);
d_node->data=d_node->data+sum;
sum=d_node->data;
convertToSumTree(d_node->l_node);
return 1;
}

void sumTree(struct TreeNode* node, int* prev, int* sum)
{
if(!node) return;
sumTree( node->right, prev, sum);
*sum += *prev;
*prev= node->data;
node->data = *sum;
sumTree(node->left,prev,sum)
}

A solution in C#

public int ReplaceNodeswithGreaterNodes(BinaryTreeNode node,int sumlargerthannode)
    {
        if (node == null) return 0;        
        int val = sumlargerthannode+ReplaceNodeswithGreaterNodes(node.Right, sumlargerthannode);
        node.item+ = val;
        ReplaceNodeswithGreaterNodes(node.Left, node.item);
        return node.item;
    }

int sum_all(node* root)
{
	if(root == NULL) return 0;
	return root->key + sum_all(root->left) + sum_all(root->right);
}

void replace_keys(node* root, int total)
{
	if(root == NULL) return;

	int leftsum = sum_all(root->left);
	root->key = sum(total - leftsum - root->key);
	
	replace_keys(root->left, total);
	replace_keys(root->right, total);
}

void replace_keys(node* root)
{
	int total = sum_all(root);
	replace_keys(root, total);
}

public class BST_greater_sum {
		int max_sum;
	
	public BST_greater_sum() {
		max_sum =0;// TODO Auto-generated constructor stub
	}
	TreeNode modify_tree(TreeNode node,int sum){
		
		
	if(node == null)
		return null;
	else
	{	
		
		modify_tree(node.rightchild, max_sum);		
		
		max_sum = max_sum + node.value;
		
		node.value = max_sum;
		modify_tree(node.leftchild, max_sum);
		
		
	}	
		
		return node;
	}

}

int sumTree(struct node *root, int sum){

if(root == NULL)
return sum;


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