Summing up all nodes
Question
This may be a simple fix - but I'm trying to sum together all the nodes (Size property from the Node class) on the binary search tree. Below in my BST class I have the following so far, but it returns 0:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return 0;
if (node.Right == null)
return sum(thisNode.Left);
if (node.Left == null)
return sum(thisNode.Right);
return sum(thisNode.Left) + sum(thisNode.Right);
}
Within my Node class I have Data which stores Size and Name in their given properties. I'm just trying to sum the entire size. Any suggestions or ideas?
Solution
It's because you're returning zero when you reach a leaf node. You should be returning the size stored in that leaf node.
In addition, if your non-leaf nodes also have a size, you'll need to process them as well thus:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
if (node.Right == null)
return thisNode.Size + sum(thisNode.Left);
if (node.Left == null)
return thisNode.Size + sum(thisNode.Right);
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
If your non-leaf nodes don't have size, use:
private long sum(Node<T> thisNode)
{
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
if (node.Right == null)
return sum(thisNode.Left);
if (node.Left == null)
return sum(thisNode.Right);
return sum(thisNode.Left) + sum(thisNode.Right);
}
A more elegant version of the first one is:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
OTHER TIPS
Maybe you meant
if (thisNode.Left == null && thisNode.Right == null)
return thisNode.Size;
?
Try this:
private long sum(Node<T> thisNode)
{
if (thisNode == null)
return 0;
return thisNode.Size + sum(thisNode.Left) + sum(thisNode.Right);
}
The only "value" that the original code ever returns is 0 - that's why the result is always 0.
How about
private long Sum(Node<T> thisNode)
{
if( thisNode == null )
return 0;
return thisNode.Size + Sum(thisNode.Left) + Sum(thisNode.Right);
}
If the size property isn't on the node itself, what about this?
public class Node<T>
{
public T Data;
public Node<T> Left;
public Node<T> Right;
public static void ForEach(Node<T> root, Action<T> action)
{
action(root.Data);
if (root.Left != null)
ForEach(root.Left, action);
if (root.Right != null)
ForEach(root.Right, action);
}
}
public interface IHasSize
{
long Size { get; }
}
public static long SumSize<T>(Node<T> root) where T : IHasSize
{
long sum = 0;
Node<T>.ForEach(root, delegate(T item)
{
sum += item.Size;
});
return sum;
}