CareerCup

1. apply reverse inorder
2. keep track of sum of nodes while traversing
3. change the value of roots while traversing

public void sumofallgreater(Node root)
    {
        if(root==null)
            return;
        sumofallgreater(root.right);
        sum+=root.info;
        root.info=sum-root.info;
        
        sumofallgreater(root.left);
        
    }

-->sum is a static variable

How about:

replaceGreater(n, sum)
{
    if (n == NIL) return;

    replaceGreater(n->right, sum);

    x = n->value;
    n->value = sum;
    sum = sum + x;

    replaceGreater(n->left, sum);
}

replaceGreater(root, 0);

in C

int sum = 0;
int old_sum;

void inRevOrder(struct Node* node)
{
	if(!node) return;
	if(node->right) inRevOrder(node->right);
	old_sum = sum;
	sum += node->val;
	node->val = old_sum;
	if(node->left) inRevOrder(node->left);
}

1) Each node will receive some values from left subtree and from right subtree.
2) That node will change its value with : selfvalue + sum of value received from right subtree
3) That node will return new pair of values to its parent: < sum of left subtree value, node's new value >
I can explain algo with an example:

left assume following BST:
		41
	40			50
39			45		55

node 40 will return <39, 40>
node 50 will return <45, (50+55)> -- <45, 105>
node 41 will receive left pair<39, 40> and right pair <45, 105>
node 41 will change -- 41 + right pair --> 41 + 45 + 105 -->191
node 41 will return <sumofleftpairvalue + newsumeofcurrentnode> -- <(39+40), 192> -- <79,192>

this will continue

sudo code:

pair<int, int> updateBst (tree *root)
{
	if (!root)	return <0,0>
	if (leafnode) return <0, root->key>

	leftpair = updateBst (root->left)
	rightpair = updateBst (root->right)

	root->key += rightpair.first + rightpair.second;
	return < (leftpair.first+leftpair.second) , root->key>
}

Reverse Inorder traversal which lists the nodes in descending followed by sum at each node works perfectly well

int sum=0;
    void descending(myBSTNode focusNode) {
        if (focusNode != null) {
            descending(focusNode.rightChild);
            sum+=focusNode.key;
            focusNode.key=sum-focusNode.key;
            System.out.println(focusNode.name + " has a key   " + focusNode.key);
            descending(focusNode.leftChild);
        }

    }

Output of Reverse Inorder traversal:

Salesman has a key 85
Sales manager has a key 75
Boss has a key 50
Secretary has a key 30
VP has a key 25
Office manager has a key 15

Final Output

Salesman has a key 0
Sales manager has a key 85
Boss has a key 160
Secretary has a key 210
VP has a key 240
Office manager has a key 265

Hi Guys, what does 'greater nodes' really means? Nodes which values are great than what it is originally? If so, in a sorted tree situation, only the right sub tree?

what do you mean by greater nodes ? Please give detail example of it.

public class ReplaceBST {

    private static List<Integer> list = new LinkedList<Integer>();
    private static List<Node>  nodeList = new LinkedList<Node>();

    public static void replace(Node root) {
        if(root == null) return;

        replace(root.left);
        list.add(root.value);
        nodeList.add(root);
        replace(root.right);
    }

    public static void inOrderTreeWalk(Node root) {
        if(root == null) return;

        inOrderTreeWalk(root.left);
        System.out.println(root.value);
        inOrderTreeWalk(root.right);
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        node4.left = node2;
        node2.left = node1;
        node1.right = node3;
        node4.right = node6;
        node6.left = node5;
        node6.right = node7;

        replace(node4);
        int cumul = 0;

        for(int i = list.size() - 1;i >= 0;i--) {
            nodeList.get(i).value = cumul;
            cumul += list.get(i);
        }

        inOrderTreeWalk(node4);

    }
}

replace_with_greater_node(self, sum):
	if self == None:
		return
	replace_with_greater_node(self.right, sum)
	temp = self.value
	sum = sum + temp
	self.value = sum
	
	replace_with_greater_node(self.left,sum)