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<Integer> list) {
create(list);
}
private void create (List<Integer> items) {
root = new TreeNode(items.get(0));
final Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode(items.get(right));
queue.add(current.right);
}
}
}
}
public static class TreeNode {
private TreeNode left;
private int item;
private TreeNode right;
TreeNode(int item) {
this.item = item;
}
}
public static class IntObject {
private int sum;
}
/**
* Computes the greater sum, provided the tree is BST.
* If tree is not BST, then results are unpredictable.
*/
public void greaterSumTree() {
if (root == null) {
throw new IllegalArgumentException("root is null");
}
computeSum (root, new IntObject());
}
private void computeSum(TreeNode node, IntObject intObj) {
if (node != null) {
computeSum(node.right, intObj);
int temp = node.item;
node.item = intObj.sum;
intObj.sum = intObj.sum + temp;
computeSum(node.left, intObj);
}
}
/**
* Returns the preorder representation for the given tree.
*
* @return the iterator for preorder traversal
*/
@Override
public Iterator iterator () {
return new PreOrderItr();
}
private class PreOrderItr implements Iterator {
private final Stack<TreeNode> stack;
public PreOrderItr() {
stack = new Stack<TreeNode>();
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.next();
}
assertTrue(Arrays.equals(expected, actual));
}
}
