Binary Search Tree Differential Keys

I asked this yesterday, but I am still completely lost and confused. I am trying to write two methods, a wrapper method and a recursive auxiliary method, named sigma(), defined as follows:

   /**
    * A wrapper method for a method that computes the
    * sum of the differential keys of this binary search tree.
    * @return the sum of the differential keys of this tree.
    */
   @Override
   public int sigma()
   {
       if (size == 0)
           return 0;
       if (root.data.getClass() != Integer.class)
           throw new IllegalArgumentException("Keys must be integers");
       return (Integer)root.data + sigma(root);
   }

   /** 
    * An auxiliary method that recursively computes the sum of
    * differential keys in the subtrees of the tree rooted at
    * the specified key.
    * @param subtreeRoot the root of a subtree of this tree
    * @return the sum of the differential keys of the left and
    * right subtrees
    */
   private int sigma(Node subtreeRoot)
   {
        // My attempt at implementing the auxiliary method
        if(subtreeRoot == null) return 0;
        return sigma(subtreeRoot.left) - (Integer)subtreeRoot.data + 
               sigma(subtreeRoot.right) - (Integer)subtreeRoot.data;
   }

Note: We are not allowed to add any parameters to either method or modify the code inside of the wrapper method.


The definition of a differential key:

Definition 1. The differential key of a node in a binary tree whose elements are integers is the element in the node if the node is the root or is the difference between the element in the node and its parent. The differential of a null node is 0.

I have covered the base case, if(subtreeRoot == null) return 0;, but after that I am confused. Here is an example of what the method should do: Example of sigma() method

The auxiliary method should return the value of the sum of all the differential keys in the BST (-1 in this example), then the wrapper method adds that value to the value of the root node (10 in this example). So the sum of the differential keys and the value returned by sigma() is 10 + (-1) = 9.

The main problem I am having is implementing a recursive solution in the auxiliary method. I can trace the solution out on paper easily, but I cannot seem to implement this into my project. I have not been able to find any resources online about this and my professor is of little help. My attempt at implementing the auxiliary method is included in the code above. Any help is appreciated.


ANSWERS:


Ok, I think I understand where the problem lies.

Let's see one example using your code.

On the node that has the 4,

sigma(subtreeRoot.left) - (Integer)subtreeRoot.data

will yield a value of -4 and

sigma(subtreeRoot.right) - (Integer)subtreeRoot.data

will return a value of -4, giving a total sigma of -8, which is wrong.

What I suggest you should do is check whether subtreeRoot.left is null BEFORE using it as part of your final result. This should be done as well for subtreeRoot.right.

I imagine your code will end up something like this:

int tot = 0;
if(subtreeRoot == null) return 0;
if (subtreeRoot.left != null)
    tot = sigma(subtreeRoot.left) - (Integer)subtreeRoot.data;
if (subtreeRoot.right != null)
    tot += sigma(subtreeRoot.right) - (Integer)subtreeRoot.data;
return tot;

I hope this helps.


What you can try is calculate the differential bottom-up. Once you updated all the nodes of the children you update the parent.

private int sigma(Node subtreeRoot)
{
    // My attempt at implementing the auxiliary method
    if(subtreeRoot == null) 
      return 0;
    else {
      if(subtreeRoot.left != null){             
        subtreeRoot.left.data = sigma(subtreeRoot.left) - subtreeRoot.data;
      }
      if(subtreeRoot.right != null){            
        subtreeRoot.right.data = sigma(subtreeRoot.right) - subtreeRoot.data;
      }


        return subtreeRoot.data;
    }

}

Note that each method call returns the original value of the node subtreeRoot and not the differential



 MORE:


 ? Binary Search Tree Differential Keys
 ? Need to present the nodes of a binary search tree through an array in Java. How do I do that?
 ? Dealing with "Keys" in Binary Search Trees
 ? Finding K largest elements in Binary Search Tree
 ? Binary Search Tree Recursive Delete
 ? Java Binary Search Tree - Recursive Void Copy Method
 ? Difficulty Constructing Binary Tree from Array
 ? Difficulty Constructing Binary Tree from Array
 ? Difficulty Constructing Binary Tree from Array
 ? Tree building function from precalculated tree