Transform a Binary Search Tree into a Greater Sum Tree
Compiler Warnings


  Iterable is a raw type. References to generic type Iterable should be parameterized


This is very easy to fix. It's horrible that you haven't fixed it already. I'm sure that you know what generics is by now so I don't need to explain it to you. Whenever you see this warning, add generics!

Iterable --> Iterable&lt;Integer&gt;

Problem solved!

Then you can get rid of the (Integer) cast next to itr.next();

Why Binary Search Tree?

My first thought, once I understood the problem your solving was: Why on earth do you have the data as a Binary Search Tree? What does the tree have to do with anything?

If this was a question given to me at an interview, I would ask them this. Why a Binary Search Tree? The operations you're doing is totally unrelated to a tree. You could just as well perform this on a regular int[]. If there is a good reason for why it has to be a Binary Search Tree then please explain it to me.

Here's a simple implementation of how to perform this on a regular int[], without using a Binary Tree:

public static void main(String[] args) {
    int[] input = new int[] { 1, 2, 7, 11, 15, 29, 35, 40  };
    int[] expected = new int[] { 139, 137, 130, 119, 104, 75, 40, 0 };
    transformToGreaterSum(input);
    System.out.println(Arrays.toString(input));
    System.out.println(Arrays.toString(expected));
}

private static void transformToGreaterSum(int[] input) {
    int sum = 0;
    for (int i = input.length - 1; i &gt;= 0; i--) {
        int prevSum = sum;
        sum += input[i];
        input[i] = prevSum;
    }
}


Note that this is also \$O(n)\$ without using any extra space.

Broken Tree

I'd also like to point out that your actual search tree does not match your image. I found out by debugging your code that your actual search tree looks like this:



The fact that it looks like this, and the fact that your algorithm works at all, is just because your input is sorted: {1, 2, 7, 11, 15, 29, 35}.

Your tree is in fact not a correct Binary Search Tree. A correct tree could look like this:



Yes, that's still a tree. It just doesn't have any left nodes (it does have seven nodes left though, I didn't remove any). A child node that is bigger than its parent should be on the right, which makes this tree right. (I love the English language)

As if that was not enough, your int[] expected says:

int[] expected = {71, 87, 89, 72, 35, 42, 0};


But your image says:

119, 137, 75, 139, 130, 104, 0, 40


Given your description:


  Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node. Diagram is here.


I would expect the node for 11 to get the value 15 + 29 + 35 + 40 = 119. I don't see 119 anywhere in your expected or actual result though...

Verifying a Binary Search Tree

As your question contains an incorrect tree and one of your comments below has an incorrect tree, I'd like to provide you with a method to verify a correct tree:

private static void verifyNode(TreeNode node) {
    if (node.left != null) {
        if (node.left.item &gt;= node.item) {
            throw new IllegalStateException("node.left &gt;= node: " + node.left.item + " &gt;= " + node.item);
        }
        verifyNode(node.left);
    }
    if (node.right != null) {
        if (node.right.item &lt;= node.item) {
            throw new IllegalStateException("node.right &lt;= node: " + node.right.item + " &lt;= " + node.item);
        }
        verifyNode(node.right);
    }
}


Just pass it your root node and it will verify your tree recursively. Note that there are two things this method does not verify, that are also a requirement for a Binary Search Tree:


There must be no duplicate nodes.
A unique path exists from the root to every other node.


Arrays and Lists

Speaking of int[] I wonder why your constructor takes a List&lt;Integer&gt; instead of an array: int[]. I don't think you gain anything by using a list.

The only thing you gain at the moment by using Integer rather than int is the possibility for this:

if (items.get(i) != null) {


As your input never contains null (and I see no reason why it should), I don't get the point of using that non-null check. I modified your code to use int[] instead and removed the non-null checks and all worked well still. It even got rid of some indentation steps and felt like a cleanup overall.

Iterate over what?

If you would have your Iterator as Iterator&lt;TreeNode&gt; instead of Iterator&lt;Integer&gt; you could use your iterator in your computeSum method as well as in your test method to fetch the results. This would make you have to modify your iterator implementation though (but as your tree is not a real binary search tree, it's quite broken already).

Or you could just ignore the tree structure and use arrays....

Summary

Given how many trees I've seen you implement, I really thought your code would be better than this. Your current code doesn't live up to your requirements, or your requirements are messed up. Additionally, the "raw type" mistake is a mistake one just should not make after having written just a few Java classes.