Return to Answer

##Overkill

##What the question is looking for

##BST

##Code Dump

Overkill

What the question is looking for

BST

Code Dump

Apart from the code style issues, I want to review your algorithm. Additionally, there are some items I believe shoudl be said in addition to Simon's comments.

As for the rest of your class, messed with a few things to simplify the testing. For a start, I made the nonde population dynamic, and it is always a BST, except for the fact that, after a re-sum, the tree is the opposite of a BST (with all items in the reverse order).

As a result, this tree is not really a BSS because it allows the structure to be invalidated (by design)

Apart from the code style issues, I want to review your algorithm. Additionally, there are some items I believe should be said in addition to Simon's comments.

As for the rest of your class, messed with a few things to simplify the testing. For a start, I made the node population dynamic, and it is always a BST, except for the fact that, after a re-sum, the tree is the opposite of a BST (with all items in the reverse order).

As a result, this tree is not really a BST because it allows the structure to be invalidated (by design)

/**
 * Computes the greater sum, provided the tree is BST.
 * If tree is not BST, then results are unpredictable.
 */
public void greaterSumTree() {
 // 0 is the sum of all the elements greater than the greatest node so far
 adjustSum (root, 0);
}
private int adjustSum(final TreeNode node, final int largerSum) {
 if (node == null) {
 return largerSum;
 }
 node.item += adjustSum(node.right, largerSum);
 return adjustSum(node.left, node.item);
}

import java.util.Arrays;
public class GreaterSumTree {
 private TreeNode root;
 public GreaterSumTree(final int[] items) {
 if (items == null || items.length == 0) {
 return;
 }
 for (int value : items) {
 add(value);
 }
 }
 
 public void add(int value) {
 TreeNode node = root;
 TreeNode addNode = new TreeNode(value);
 while (node != null) {
 if (value < node.item) {
 if (node.left == null) {
 node.left = addNode;
 return;
 }
 node = node.left;
 } else {
 if (node.right == null) {
 node.right = addNode;
 return;
 }
 node = node.right;
 }
 }
 // no nodes to add to. Must be root.
 root = addNode;
 }
 public static class TreeNode {
 private TreeNode left;
 private int item;
 private TreeNode right;
 TreeNode(int item) {
 this.item = item;
 }
 }
 /**
 * Computes the greater sum, provided the tree is BST.
 * If tree is not BST, then results are unpredictable.
 */
 public void greaterSumTree() {
 adjustSum (root, 0);
 }
 private int adjustSum(TreeNode node, int largerSum) {
 if (node == null) {
 return largerSum;
 }
 node.item += adjustSum(node.right, largerSum);
 return adjustSum(node.left, node.item);
 }
 
 public int[] toArray() {
 IntArray array = new IntArray();
 
 addToArray(root, array);
 
 return array.getArray();
 
 }
 
 private void addToArray(TreeNode node, IntArray array) {
 if (node == null) {
 return;
 }
 addToArray(node.left, array);
 array.add(node.item);
 addToArray(node.right, array);
 }
 private static final class IntArray {
 private int[] data = new int[128];
 private int size = 0;
 
 public void add(int value) {
 if (size == data.length) {
 data = Arrays.copyOf(data, size + (size >> 2) + 16);
 }
 data[size++] = value;
 }
 
 public int[] getArray() {
 return Arrays.copyOf(data, size);
 }
 }
 
 public static void main(String[] args) {
 int[][] data = {
 { 0,1,2,3,4,5},
 { 4,8,66,4,1,2,6,0,1,0}
 };
 for (int[] items : data) {
 GreaterSumTree gst = new GreaterSumTree(items);
 int[] pre = gst.toArray();
 gst.greaterSumTree();
 int[] post = gst.toArray();
 System.out.printf("Processed %s%n initial: %s%n post: %s%n", Arrays.toString(items), Arrays.toString(pre), Arrays.toString(post));
 }
 }
}

/**
 * Computes the greater sum, provided the tree is BST.
 * If tree is not BST, then results are unpredictable.
 */
public void greaterSumTree() {
 adjustSum (root, 0);
}
private int adjustSum(TreeNode node, int largerSum) {
 if (node == null) {
 return largerSum;
 }
 int current = node.item;
 node.item = adjustSum(node.right, largerSum);
 return adjustSum(node.left, node.item + current);
}

##Code Dump

import java.util.Arrays;
public class GreaterSumTree {
 private TreeNode root;
 public GreaterSumTree(final int[] items) {
 if (items == null || items.length == 0) {
 return;
 }
 for (int value : items) {
 add(value);
 }
 }
 
 public void add(int value) {
 TreeNode node = root;
 TreeNode addNode = new TreeNode(value);
 while (node != null) {
 if (value < node.item) {
 if (node.left == null) {
 node.left = addNode;
 return;
 }
 node = node.left;
 } else {
 if (node.right == null) {
 node.right = addNode;
 return;
 }
 node = node.right;
 }
 }
 // no nodes to add to. Must be root.
 root = addNode;
 }
 public static class TreeNode {
 private TreeNode left;
 private int item;
 private TreeNode right;
 TreeNode(int item) {
 this.item = item;
 }
 }
 /**
 * Computes the greater sum, provided the tree is BST.
 * If tree is not BST, then results are unpredictable.
 */
 public void greaterSumTree() {
 adjustSum (root, 0);
 }
 private int adjustSum(TreeNode node, int largerSum) {
 if (node == null) {
 return largerSum;
 }
 int current = node.item;
 node.item = adjustSum(node.right, largerSum);
 return adjustSum(node.left, node.item + current);
 }
 
 public int[] toArray() {
 IntArray array = new IntArray();
 
 addToArray(root, array);
 
 return array.getArray();
 
 }
 
 private void addToArray(TreeNode node, IntArray array) {
 if (node == null) {
 return;
 }
 addToArray(node.left, array);
 array.add(node.item);
 addToArray(node.right, array);
 }
 private static final class IntArray {
 private int[] data = new int[128];
 private int size = 0;
 
 public void add(int value) {
 if (size == data.length) {
 data = Arrays.copyOf(data, size + (size >> 2) + 16);
 }
 data[size++] = value;
 }
 
 public int[] getArray() {
 return Arrays.copyOf(data, size);
 }
 }
 
 public static void main(String[] args) {
 int[][] data = {
 { 0,1,2,3,4,5},
 { 11,2,29,1,7,15,40,35},
 { 4,8,66,4,1,2,6,0,1,0}
 };
 for (int[] items : data) {
 GreaterSumTree gst = new GreaterSumTree(items);
 int[] pre = gst.toArray();
 gst.greaterSumTree();
 int[] post = gst.toArray();
 System.out.printf("Processed %s%n initial: %s%n post: %s%n", Arrays.toString(items), Arrays.toString(pre), Arrays.toString(post));
 }
 }
}