Reputation: 129
Binary Search Tree Sum of Differential Keys
I am trying to implement a method named sigma() into a binary search tree class. The job of this method is to return the sum of the differential keys in the BST. The definition I was given is as follows:
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. See figure 1 for an illustration of a differential binary tree. The sum of the differential keys of T is 9, ∑i=1n ∆(i), where ∆(i) denotes the differential key of node i and n, the size of the tree.
The method should return the sum of the tree sigma(T)'s values. So in this case, sigma(T) would return 10-4-2+3+5-3 = 9. I understand the concept behind all of this and can easily do it on paper, but implementing it into my code is what I am having trouble with. I am required to write a wrapper method and a recursive, auxiliary method to define sigma().
Here is my BSTree class I have written so far (sigma() is towards the bottom):
package bstreedemo;
import java.util.function.Function;
/**
* A binary search tree <br>
* Requires JDK 1.8 for Function
* @param <E> the tree data type
* @since 12/09/2016
* @see BSTreeAPI
*/
public class BSTree<E extends Comparable<E>> implements BSTreeAPI<E>
{
/**
* the root of this tree
*/
private Node root;
/**
* the number of nodes in this tree
*/
private int size;
/**
* A node of a tree stores a data item and references
* to the child nodes to the left and to the right.
*/
private class Node
{
/**
* the data in this node
*/
public E data;
/**
* A reference to the left subtree rooted at this node.
*/
public Node left;
/**
* A reference to the right subtree rooted at this node
*/
public Node right;
}
/**
* Constructs an empty tree
*/
public BSTree()
{
root = null;
size = 0;
}
@Override
public boolean isEmpty()
{
return size == 0;
}
@Override
public void insert(E item)
{
Node newNode = new Node();
newNode.data = item;
if (size == 0)
{
root = newNode;
size++;
}
else
{
Node tmp = root;
while (true)
{
int d = tmp.data.compareTo(item);
if (d == 0)
{ /* Key already exists. (update) */
tmp.data = item;
return;
}
else if (d>0)
{
if (tmp.left == null)
{ /* If the key is less than tmp */
tmp.left = newNode;
size++;
return;
}
else
{ /* continue searching for insertion pt. */
tmp = tmp.left;
}
}
else
{
if (tmp.right == null)
{/* If the key is greater than tmp */
tmp.right = newNode;
size++;
return;
}
else
{ /* continue searching for insertion point*/
tmp = tmp.right;
}
}
}
}
}
@Override
public boolean inTree(E item)
{
return search(item) != null;
}
@Override
public void remove(E item)
{
Node nodeptr = search(item);
if (nodeptr != null)
{
remove(nodeptr);
size--;
}
}
@Override
public void inorderTraverse(Function func)
{
inorderTraverse(root,func);
}
@Override
public E retrieve(E key) throws BSTreeException
{
if (size == 0)
throw new BSTreeException("Non-empty tree expected on retrieve().");
Node nodeptr = search(key);
if (nodeptr == null)
throw new BSTreeException("Existent key expected on retrieve().");
return nodeptr.data;
}
@Override
public int size()
{
return size;
}
/**
* A recursive auxiliary method for the inorderTraver method that
* @param node a reference to a Node object
* @param func a function that is applied to the data in each
* node as the tree is traversed in order.
*/
private void inorderTraverse(Node node, Function func)
{
if (node != null)
{
inorderTraverse(node.left,func);
func.apply(node.data);
inorderTraverse(node.right,func);
}
}
/**
* An auxiliary method that support the remove method
* @param node a reference to a Node object in this tree
*/
private void remove(Node node)
{
E theData;
Node parent, replacement;
parent = findParent(node);
if (node.left != null)
{
if (node.right != null)
{
replacement = node.right;
while (replacement.left != null)
replacement = replacement.left;
theData = replacement.data;
remove(replacement);
node.data = theData;
return;
}
else
replacement = node.left;
}
else
{
if (node.right != null)
replacement = node.right;
else
replacement = null;
}
if (parent==null)
root = replacement;
else if (parent.left == node)
parent.left = replacement;
else
parent.right = replacement;
}
/**
* An auxiliary method that supports the search method
* @param key a data key
* @return a reference to the Node object whose data has the specified key.
*/
private Node search(E key)
{
Node current = root;
while (current != null)
{
int d = current.data.compareTo(key);
if (d == 0)
return current;
else if (d > 0)
current = current.left;
else
current = current.right;
}
return null;
}
/**
* An auxiliary method that gives a Node reference to the parent node of
* the specified node
* @param node a reference to a Node object
* @return a reference to the parent node of the specified node
*/
private Node findParent(Node node)
{
Node tmp = root;
if (tmp == node)
return null;
while(true)
{
assert tmp.data.compareTo(node.data) != 0;
if (tmp.data.compareTo(node.data)>0)
{
/* this assert is not needed but just
in case there is a bug */
assert tmp.left != null;
if (tmp.left == node)
return tmp;
tmp = tmp.left;
}
else
{
assert tmp.right != null;
if (tmp.right == node)
return tmp;
tmp = tmp.right;
}
}
}
/********************* Method Begins Here **********************/
/**
* 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)
{
if(subtreeRoot == null)
return 0;
if(subtreeRoot.left != null)
{
if(subtreeRoot.right != null)
{
return (Integer)subtreeRoot.data + sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
}
else
return (Integer)subtreeRoot.data + sigma(subtreeRoot.left);
}
if(subtreeRoot.right != null)
return sigma(subtreeRoot.right) - (Integer)subtreeRoot.data;
return (Integer)subtreeRoot.data;
}
/********************* Method Ends Here **********************/
/**
* Determines whether this binary tree is perfect
* @return true if the binary tree is perfect, otherwise false
*/
@Override
public boolean isPerfect()
{
}
/**
* A wrapper method that computes the height of this tree
* @return the height of this tree
*/
@Override
public int height()
{
return height(root);
}
/**
* An auxiliary method that recursively computes
* the height of the subtree rooted at the specified node.
* @param node a root of a subtree
* @return the height of this tree
*/
private int height(Node node)
{
if(node == null)
return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
/**
* Determines whether this binary tree is complete.
* @return true if this binary tree is complete, otherwise false
*/
@Override
public boolean isComplete()
{
}
/**
* An auxiliary method that recursively determines whether
* the index of the subtree rooted at the specified node is
* less than the size of this tree.
* @param node a root of a subtree
* @param index the index of this node
* @return
*/
private boolean isComplete(Node node, int index)
{
}
}
The wrapper method returns the data of the root node, casting it as an Integer, added to the value returned by the auxiliary method performed on the root node.
I figure there are three cases to account for:
if(subtreeRoot == null)if(subtreeRoot.left != null && subtreeRoot.right != null) // Parent node has left and right child nodesif(subtreeRoot.left != null || subtreeRoot.right != null) // Parent node has only left or right child node
This is where I am stuck, cases 2 and 3. I know the goal is to subtract the left and/or right child's value(s) from the value of the parent node to find the value(s) of the differential key for that subtree, then recurse down the left and/or right remaining subtrees performing the same operation and adding up the results. But I don't know where to go from here. We are not allowed to add parameters/arguments to the methods for the project, so (Node subtreeRoot) is the only parameter allowed for the auxiliary method and the wrapper method takes no parameters. Would it be useful to create a Function<> to simplify the problem, is my logic flawed, etc.? Any help or further explanation is appreciated, as I'm a bit lost at this point and my professor is of no help.
Upvotes: 1
Views: 626
Answers (2)
Reputation: 50
You must be someone in my class... Anyways, you have to use the findParent method since you don't pass the parent node in the sigma method.
private int sigma(Node subtreeRoot) {
int tot = 0;
if (subtreeRoot == null) {
return 0;
}
if (findParent(subtreeRoot) == null) {
tot = sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
} else{
tot = (Integer) subtreeRoot.data - (Integer) findParent(subtreeRoot).data
+ sigma(subtreeRoot.left) + sigma(subtreeRoot.right);
}
return tot;
}
The if-statement using the findParent method is because the method will return null due to subtreeRoot being the root of the tree and as such, it has no parent. Then, when you called the sigma method for the left and right children, they will follow through to the else-statement.
I'm stuck on the isPerfect method. I can do it if I create an aux method and use recursion, but we're not supposed to do that...
Upvotes: 1
Reputation: 77837
You're making the main logic far to complex, as MrMcGreg has already pointed out.
- Base case: If the tree passed in is NULL, return 0
- Recursion: return the sum of
- node value minus parent node value
- sigma(left child)
- sigma(right child)
Since a node has no link to its parent, your recursive function will need to pass the parent's value into the routine. You'll get code derived from this pseudo-code:
int sigma_aux (node root, int parent_val) {
if !node
return 0
else
root_val = root->data
return root_val - parent_val +
sigma_aux(root->left , root_val) +
sigma_aux(root->right, root_val)
That's it; just a base case and a recursion case. Trace it with pencil and paper until you understand it -- then go implement it within the context of your code.
OP wrote:
... something like
return (Integer) subtreeRoot.data - (Integer) root.data + sigma(subtreeRoot.left) + sigma(subtreeRoot.right);? I don't understand how to get the value of the parent node. I thought the parent node was the subtreeRoot node passed into the auxiliary method and it's children were subtreeRoot.left and subtreeRoot.right
You control what is passed into the auxiliary method; don't take your first concept as a given. This is where you're getting confused. Simplify that: the only real purposes of the top-level sigma is to pass the tree root's data to sigma_aux, and to do the top-most computation to return to the outside world.
int sigma (node root) { root_val = root->data;
After this, it looks just like sigma_aux.
Upvotes: 1
Related Questions
- Vertical Sum in a given Binary Tree
- Binary Tree branch sums without recursion
- Range Sum of BST using DFS
- Checking if sum exists in tree path using recursion
- Summing elements of binary tree in Java
- Calculating sums in tree structures using caching
- given a definition of node, calculate the sum of the nodes in binary tree
- Find paths in a binary search tree summing to a target value
- Sum values in binary tree of integers weighted by depth
- Tree - path sum