CareerCup

First traverse the tree and store the node values in an ArrayList (basically an array).
Then sort the ArrayList. Then iterate the ArrayList backwards, while keeping track of the
total value so far. In each iteration, I store (current value, total) into a hash table.
So an entry (5, 27) would mean the sum of values >= 5 in the tree is 27.
Finally, I iterate through the tree again. When I see a node with say value 5, I would replace it with value 27.

static void replaceValues(Tree t) {
  ArrayList<Integer> lst = new ArrayList<Integer>();
  traverse(t, lst);
  Collections.sort(lst);
  int total = 0;
  HashMap<Integer, Integer> values = new HashMap<Integer, Integer>();
  for(int i=lst.size()-1; i>=0; i--) {
    int value = lst.get(i);
    total += value;
    values.put(value, total);
  }
  replace(t, values);
}

static void traverse(Tree t, ArrayList<Integer> lst) {
  if(t == null)
    return;
  lst.add(t.value);
  traverse(t.left, lst);
  traverse(t.right, lst);
}

static void replace(Tree t, HashMap<Integer, Integer> values) {
  if(t == null)
    return;
  t.value = values.get(t.value);
  replace(t.left, values);
  replace(t.right, values);
}

1. traverse binary tree in an array say A and sort it
2. maintain another array and now start adding 1 array elements from last index of previous array
3. now search value in tree form 1 array and then replace that value in tree from the same index value in 2 array
Time Complexity of this algorithm is o(nlogn) and space complexity is o(n)
however,if we had BST instead of binary tree,the time complexity can be modified to o(n) and space complexity to o(1)(ignoring recursion stack space)

one of the solutions is to do with two stacks

1) Any x-order traversal would work. Take preorder
2) if stack1 is null. push the current node pointer
3) if stack1 is not null, pop the elements from stack1 until lesser element is found or null and push these elements on to stack2.
4) push the current node pointer. and pop elements from stack2 and push them to stack1.(this can be optimized)
5) Repeat this until the traversal is completed
6) Now pop the elements from the stack1 and sum them while popping and store them.

1. Traverse tree and store it in array and sort it.( O(nlogn) ).
2. Start post order traversal of tree and for each node through binary search find greater or same value in sorted array and update the root value.

void InorderNodeSaved(struct bst *b, int *values, int &index)
{
	if(b)
	{
		InorderNodeSaved(b->lc,values,index);
		values[index++]=b->data;
		InorderNodeSaved(b->rc,values, index);
	}
}

void UpdateNodesValuesBySumNodesGreatedThanEqual(struct bst *b, int *values, int &index)
{
	if(b)
	{
		UpdateNodesValuesBySumNodesGreatedThanEqual(b->lc,values,index);
		b->data=values[index++];
		UpdateNodesValuesBySumNodesGreatedThanEqual(b->rc,values,index);
	}
}

void UpdateValues(int *values, int index)
{
	int	sum=0;
	for(int i=index-1;i>=0;i--)
	{
		values[i]+=sum;
		sum=values[i];
	}
}

we can traverse a tree in reverse inorder traversal and can do the same.

void modifyTree(node* head, int* sum)  {
        if(head->left == NULL && head->right == NULL) {
             return;
        }

        modifyTree(head->right, sum);
        head->data += *sum;
        *sum = head->data;
        modifyTree(head->left, sum);

}

//following function called for each node
void findSum(Node* ptr)
{
if(ptr==NULL)
{
return;
}
current_node_sum=ptr->data+doSum(ptr->left,ptr->data)+doSum(ptr->right,ptr->data);
}

int doSum(Node* ptr,int val)
{
if(ptr==NULL)
{
return NULL;
}

int sum=doSum(ptr->left,val) + doSum(ptr->right,val);
if(ptr->data>val)
{
return ptr->data+sum;
}
else
{
return sum;
}

}

1. store inorder traversal of binary tree in an array say A and sort it
2. now again make any traversal, and for each node search the node's value in the array. Let the position of the element be i. So add the elements from i+1 to end with the node's value
Time Complexity of this algorithm is o(nlogn) and space complexity is o(n)
however,if we had BST instead of binary tree,the time complexity can be modified to o(n) and space complexity to o(1)(ignoring recursion stack space)