Transform a Binary Search Tree into a Greater Sum Tree

Given a Binary Search Tree (where all nodes on the left child branch are less than the node), and all nodes to the right are greater/equal to the node), transform it into a Greater Sum Tree where each node contains sum of it together with all nodes greater than that node. Example diagram is here:

Looking for code review, optimizations and best practices.

public class GreaterSumTree implements Iterable {

    private TreeNode root;

    public GreaterSumTree(List list) {
        create(list);
    }

    private void create (List items) {
        root = new TreeNode(items.get(0));

        final Queue queue = new LinkedList();
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i  stack;

        public PreOrderItr() {
            stack = new Stack();
            stack.add(root);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException("No more nodes remain to iterate");

            final TreeNode node = stack.pop();           

            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);

            return node.item;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Invalid operation for pre-order iterator.");
        }
    }
}

Here is a test case:

```
public class GreaterSumTreeTest {

@Test
public void test() {
Integer[] a = {1, 2, 7, 11, 15, 29, 35};
GreaterSumTree greaterSumTree = new GreaterSumTree(Arrays.asList(a));
greaterSumTree.greaterSumTree();

int[] expected = {71, 87, 89, 72, 35, 42, 0};
int[] actual = new int[a.length];
int counter = 0;
Iterator itr = greaterSumTree.iterator();
while (itr.hasNext()) {
actual[counter++] = (Integer) itr.n

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

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 >= 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 >= node.item) {
            throw new IllegalStateException("node.left >= node: " + node.left.item + " >= " + node.item);
        }
        verifyNode(node.left);
    }
    if (node.right != null) {
        if (node.right.item <= node.item) {
            throw new IllegalStateException("node.right <= node: " + node.right.item + " <= " + 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 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 instead of Iterator 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 m

StackExchange Code Review Q#55966, answer score: 18