﻿ Binary Search Tree Differential Keys

# 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:

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.

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

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;