CareerCup

Traversing right node then center and left.While traversing add the node values.

Code:

int sum = 0;
	public void changeTree(BinaryTree root) {
		if (root != null) {
			changeTree(root.right);
			root.data = sum + root.data;
			sum = root.data;
			changeTree(root.left);
		}
	}

I think we can use the following algorithm. Traverse the tree reversely. add the successors value together.
we need to consider several conditions.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace A2013042001
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
            Tree t = new Tree(array);
            t.BST();
            t.Traverse(t.root, 0);
            t.BST();
            Console.Read();
        }
    }

    class Node
    {
        public int value;
        public Node left;
        public Node right;
        public Node(int val)
        {
            value = val;
            left = null;
            right = null;
        }
    }

    class Tree
    {
        public Node root;

        public Tree(int[] array)
        {
            root = CreateTree(array, 0, array.Length - 1);
        }

        private Node CreateTree(int[] array, int start, int end)
        {
            if (start > end)
            {
                return null;
            }
            int middle = (start + end) / 2;
            Node n = new Node(array[middle]);
            n.left = CreateTree(array, start, middle - 1);
            n.right = CreateTree(array, middle + 1, end);
            return n;
        }

        public int Traverse(Node n, int currentsum)
        {
            int sumrightchild = currentsum;
            if (n.right != null)
            {
                sumrightchild = Traverse(n.right, currentsum);
            }
            n.value = n.value + sumrightchild;
            if (n.left != null)
            {
                return Traverse(n.left, n.value);
            }
            return n.value;
        }

        public void BST()
        {
            int count = 1;
            int times = 1;
            ArrayList now = new ArrayList();
            now.Add(root);
            while (now.Count > 0)
            {
                Node cur = (Node)now[0];
                now.RemoveAt(0);
                if (cur.left != null)
                {
                    now.Add(cur.left);
                }
                if (cur.right != null)
                {
                    now.Add(cur.right);
                }
                Console.Write(cur.value+",");
                count--;
                if (count == 0)
                {
                    times = times * 2;
                    count = times;
                    Console.WriteLine();
                }
            }
        }
    }
}

Traverse using modified depth first search - going through the right subtree first .
And start finding the new value for each node by using following
New value of current node = (old value of current node + new value of the right child + new value of parent if current node is the left child)

we can use reverse inorder traversal

Pretty much same idea as Ankita, where each recursive call does 2 things:
(1) Replace the values for all nodes falling under the current node (including the current node)
(2) Return the new value of the leftmost descendant falling under the current node

static int sumGreater(Node node, int n) {
    if(node == null)
      return n;
    node.value += n;
    node.value += sumGreater(node.right, 0);
    return sumGreater(node.left, node.value);
  }

C++ code

#include<iostream>
#include<vector>
struct node {
        int value;
        struct node *left;
        struct node *right;

        node(int a) {
                value = a;
                left = NULL;
                right = NULL;
        }
};

node *createBST(std::vector<int> numbers, int low, int high) {
        // create tree from numbers
        if (low > high) return NULL;

        int mid = (low + high) / 2;
        node *root = new node(numbers[mid]);
        root->left = createBST(numbers, low, mid -1);
        root->right = createBST(numbers, mid+1, high);
        return root;

}

void printHeight(node* root) {
    static int height = 0;
    height++;
    if(root == NULL) {
        height--;
        return;
    }   
    printHeight(root->left);
    for(int i = 1; i <= height; i++) 
        std::cout << "\t";
    std::cout << root->value << "\n";
    printHeight(root->right);
    height--;
}      

void replaceNodeWithSumGreater(struct node* root) {
	static int n = 0;
	if(root == NULL) return;
	
	replaceNodeWithSumGreater(root->right);
	n += root->value;
	root->value = n;
	replaceNodeWithSumGreater(root->left);
}	



int main() {
	std::cout << "Enter numbers\n";
	std::vector<int> numbers;
	int temp = 0;
	while(std::cin >> temp) {
		numbers.push_back(temp);
	}

	node *root = createBST(numbers, 0, numbers.size() - 1);
	
	(void) 	printHeight(root);
	
	replaceNodeWithSumGreater(root);
	
	(void) 	printHeight(root);
	return 0;
}

public class BST {
    public static class Node {
        int value;
        Node left;
        Node right;
    }
    private Node root;
    private int replaceWithHigherNodeSum(Node node, int sumSoFar) {
        if (node.right != null) {
            sumSoFar = replace(node.right, sumSoFar);
        }
        sumSoFar += node.value;
        node.value = sumSoFar;
        if (node.left != null) {
            sumSoFar = replace(node.left, sumSoFar);
        }
        return sumSoFar;
    }
    public void replaceWithHigherNodeSum() {
        if (root == null) {
            return;
        }
        replaceWithHigherNodeSum(root, 0);
    }
}

Start: sumAllLarge(root,0)

public static int sumAllLarge(Node n, int pv) {
		if (n == null) {
			return 0;
		}
		int rv = sumAllLarge(n.r, pv);
		n.v = n.v + pv + rv;
		int lv = sumAllLarge(n.l, n.v);
		return n.v > lv ? n.v : lv;
	}

This question can be done very simply in three lines if you use recursion. The basic method is to go as right as possible down the tree, and only when you can't go anymore right, then start adding the sum. At the right most node (where we are starting to add the sum), traverse to the left child (if it exists).

Here is the code (in C++)

int rwsg(Node *r, int sg) {
	if (!r) return sg;
	r->val += rwsg(r->right, sg);
	return rwsg(r->left, r->val);
}

int main() {
	rwsg(r, 0); //start with 0 for sg
}

The above looks really simple, but it works. Take the examples given above and go over them using this algorithm by hand.

public void changeTree(BinaryTree root, int rightSum) {

		if (root != null) return 0;

		int rightValue  = changeTree(root.right, rightSum);
		root.data += rightValue + rightSum;
		changeTree(root.left, root.data);

		return root.data;
	}


initial call should be changeTree(root, 0);

Step 1: Traverse preorder(depth first) and calculate the sum of the roots left child + root's right child if they exist, so after traversing the full tree each node will have a sum of all the nodes of its left subtree and right subtree,

Step2: Traverse the tree again and from each node eliminate the value of its left child if it exists.

O(2n) : Time Complexity, O(n) space Complexity

Even I was asked solve this question. I did with reverse in order. But the reverse in order won't work if the tree has duplicate elements such as:
4
4 4

Please post if anyone has the correct algorithm..

void node_change(Node *new)
{
if(node==NULL)
return 0;
else
node->data+=(node_change(node->left)>=node->data?return (node->left->data):return 0;)+(node_change(node->right)>=node->data?return node_change(node->right->data):return 0; );
}

int sumlessThan(pbnode node,int *n)
{
	if(node==NULL)
		return 0;
	sumlessThan(node->right,n);
	sumlessThan(node->left,n);
	*n += node->data;
	node->data = *n;
}