CareerCup

Reverse inorder traversal. right->root->left. Calculate the sum and pass to left node.

public int sumGreaterNodes(Node node, int sum){
    if (node == null)
      return sum;
    
    int rs = sumGreaterNodes(node.getRight(), sum);
    int cs = node.getKey() + rs;
    node.setKey(cs);
    int ls = sumGreaterNodes(node.getLeft(), cs);
    return ls;
  }

sumGreaterNodes(root, 0);

Anybody can tell if this approach was good enough ?

I also considered the reverse in-order traversal that geekvjaks mentioned. Here's my version:

void sumGreaterNodes(Node n, IntWrap sum) {

	if (n.right != null)
		sumGreaterNodes(n.right, sum);

	n.greaterValuesSum = sum.value;
	sum.value += n.value;

	if (n.left != null)
		sumGreaterNodes(n.left, sum);
}

class IntWrap {
	public int value;
}

What is meant by "You have to compute for each node the summation of all nodes whose value is greater than the current node." ?

Do I have to find all nodes whose value is less than the sum of its children?

class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.val = value

class Tree:
    def __init__(self):
        self.root = None

    def add(self, value):
        node = Node(value)
        if not self.root:
            self.root = node
        else:
            current = self.root
            while (True):
                if current.val < node.val:
                    if not current.right:
                        current.right = node
                        break
                    current = current.right 
                else:
                    if not current.left:
                        current.left = node
                        break
                    current = current.left

    def helperSum(self, current, value): 
        s = 0 
        if current:
            if current.left and current.left.val > value:
                s = s + self.helperSum(current.left, value)
            if current.val > value:
                s = s + current.val
            if current.right:
                s = s + self.helperSum(current.right, value)
        return s

    def getSum(self, value):
        return self.helperSum(self.root, value)

An inorder traversal starting from the rightmost node.
Right Node- Node- Left Node.

public static int inorderSum(Tree t,int sum)
{
    if(t!=null)
    {
        sum=inorderSum(t.right,sum);
           sum=sum + t.data;
       t.data=sum;
        System.out.print(t.data+" ");
   	sum=inorderSum(t.left,sum);
    }
	return sum;
}

How about just using BFS and summing all the nodes whose value is greater that the given nodes value.

Another approach: Modify preorder traversal such that root.left is only sent in recursive call if it is greater that the given node's value.