CareerCup

int visit(Node n, int add) {
    if (n == null) {
      return add;
    }
    int curVal = n.data;
    n.data = visit(n.right, add);
    return visit(n.left, n.data + curVal);
  }

   void visit(Node root) {
    visit(root, 0);
  }

public static int sumTree(Tree root, int sum) {
	if (root == null)
		return sum;
	sum = sumTree(root.right,sum);
	root.value+=sum;
	sum = sumTree(root.left,root.value);
	return sum;
}

Here is a solution that takes O(n) time:
The idea is that we recurse the tree and we go updating every node's value. We pass a parameter called greater, which stores the sum of the values that are greater than the current node (and are coming from a different part of the tree). So when we call the recursion on a left subtree, we pass to it the sum of the nodes that a greater than it (but not part of this left subtree).
Also, the recursive function returns the sum of the nodes in the tree, which we use to calculate the new values of the nodes.

public void changeValues(Node root) {
	changeValues(root, 0);
}

public int changeValues(Node root, int greater) {
	if(root == null)
		return 0;
	tmp = root.value;
	int right = changeValues(root.right, greater);
	root.value = right + greater;
	int left = changeValues(root.left, root.value + tmp);
	return left + tmp + right;
}

Since we are not allowed to create global or static variable, we can create hashmap(dictionary) datastructure, to maintain the key-value pair with key as nodevalue and value as sum of values of node greater than the node and while recurssive call, we will keep on sending this hashmap as an argument and using this hashmap, we will keep on updating the value.
Please let me know if this is right approach.

// C program to find sum of all paths from root to leaves
#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left, *right;
};

// function to allocate new node with given data
struct node* newNode(int data)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int sumOfRightsUtil(struct node* root, int inSum) {
	if (root == NULL)
		return 0;

	int rightSum = sumOfRightsUtil(root->right, inSum);
	int leftSum = sumOfRightsUtil(root->left, inSum + rightSum + root->data);

	int returnSum  = leftSum + rightSum + root->data;

	root->data = root->data + rightSum + inSum;

	return returnSum;
}

void printInorder(struct node* root) {
	if (NULL != root) {
		printInorder(root->left);
		printf("%d, ", root->data);
		printInorder(root->right);
	}
}

void sumOfRights(struct node* root) {
	int sum = sumOfRightsUtil(root, 0);
}

// Returns sum of all root to leaf paths. The first parameter is root
// of current subtree, the second parameter is value of the number formed
// by nodes from root to this node

// Driver function to test the above functions
int main()
{
    struct node *root = newNode(6);
    root->left        = newNode(3);
    root->right       = newNode(5);
    root->right->right= newNode(7);
    root->left->left  = newNode(2);
    root->left->right = newNode(5);
    root->right->right = newNode(4);
    root->left->right->left = newNode(7);
    root->left->right->right = newNode(4);
    printInorder(root);
    sumOfRights(root);
    printf("\n");
    printInorder(root);
    return 0;
}

When we do reverse inorder traverse of BST, that is right--root--left, the nodes visited before current node are those having greater value. By keeping a record of the sum of all nodes visited, we can easily fix the problem.
Following is C code:

void replaceWithSumOfAllGreater(TreeNode* root, int* pSum)
{
	if(root == NULL) return;
	replaceWithSumOfAllGreater(root->right, pSum);
	int tmp = *pSum + root->val;
	root->val = *pSum;
	*pSum = tmp;
	replaceWithSumOfAllGreater(root->left, pSum);
}
void replaceWithSumOfAllGreater(TreeNode* root)
{
	int sum = 0;
	replaceWithSumOfAllGreater(root, &sum);
}

if(root != null) {
		updateNodeValue(root, 0);
	}
	
	void updateNodeValue(Node n, int val) {
		n.data = n.data + val;
		if(n.left != null) {
			updateNodeValue(n.left, n.data);
		}
		if(n.right != null) {
			updateNodeValue(n.right, n.data);
		}
	}

what about we do in-order traversal iteratively and store the node's value in a array list and at the same time using a hash map store the value-node. After the traversal, update the array list by calculating the sum and then update the node using hash map?

I think this would work fine:
1. Do inorder traversal and push each node into a stack
2. set sum=0
3. pop the Nodes from stack and do
temp = node.data;
node.data = sum;
sum += temp;

This takes O(n) time and space.

This is a twisted inorder traversal question:

public int inOrder(Node node, int sum)
{
	if(node == null)
	{
		return 0;
	}
	sum += inOrder(node.right, sum);
	int t = node.data;
	node.data = sum;
	sum += t;
	sum += inOrder(node.left, sum);
	return sum;
}

From main, just call inOrder(root,0);

void reverseorder(tNode *n, int& sum) {
  if (n == NULL)
      return;

  reverseorder(n->right, sum);
  int tmp = sum;
  sum += n->data;
  n->data = tmp;
  reverseorder(n->left, sum);
}

Its bascially reverse inorder traversal. But we also need to clarify, in case there are duplicate nodes, whether to consider those while adding up .. This code does not care of duplicate nodes

public int add(Node root,int sum){
	if(root.right != null) sum = add(root.right,sum);
	if(root != null){
		root.data += sum;
		sum = root.data;
	}
	if(root.left != null) sum = add(root.left,sum);
	return sum;
}

:) Inorder traversal gives the tree in sorted order: L(D) R ... if we reverse the calls to right and left, we can get the same in reverse sorted order ... so now ... just before printing, one can keep count of how already printed. O(n) solution. Very simple.

public static int ModifyNodeData(Node node,int data)
{
int res=0;

if(node!=null)
{
int r = ModifyNodeData(node.right,data);

if(r>0)
res =node.data+r;
else
res=node.data+data;
node.data =res;
int l =ModifyNodeData(node.left,res);
if(l>0)
return l;
else
return res;
}
return res;

}

int ModifyNodeData(Node node,int data)
	{		int res=0;
			if(node!=null)
		{
			int r = ModifyNodeData(node.right,data);
				if(r>0)
			res =node.data+r;
			else
				res=node.data+data;
			node.data =res;
		    int l =ModifyNodeData(node.left,res);
			if(l>0)
				return l;
			else
			return res;
		}
		return res;
	}

public static int ModifyNodeData(Node node,int data)
{ int res=0;
if(node!=null)
{
int r = ModifyNodeData(node.right,data);
if(r>0)
res =node.data+r;
else
res=node.data+data;
node.data =res;
int l =ModifyNodeData(node.left,res);
if(l>0)
return l;
else
return res;
}
return res;
}

public static int chSum(TNode node){
		if(node == null){
			return 0;
		}else if(node.left == null && node.right == null){
			return node.value;
		}else{
			int  tmp = node.value;
			node.value = chSum(node.right);
			return tmp + node.value + chSum(node.left);
		}
	}