Tree, does the value equal sum (Boolean output)

Question

The question is:

We define a "root-to-leaf path" to be any sequence of nodes in a tree starting with the root node and proceeding downward to a leaf. The "root-to-leaf path sum" for that path is the sum of all the nodes (including the root) along that path. Define an empty tree to contain no root-to-leaf paths (and so its sum is zero). Define a tree with one node to have a root-to-leaf path consisting of just the root (and so its sum is the value of the root). Given a binary tree and a value "sum", return true if the tree has some root-to-leaf path such that adding up all the values along the path equals "sum". Return false if no such path can be found.

and I have:

public  boolean BTpathsum(BinNode root, int sum)
{
        if(root==null)
{
    return false;
}
else if(root.value() == sum){
 return true;
}
else{
    return BTpathsum(root.left, sum - root.value()) || BTpathsum(root.right, sum - root.value());
}
}

Why is this turning out incorrect for me?

Logan Kirkendoll Logan Kirkendoll · Accepted Answer · 2017-04-13T03:35:02

Here you go

public boolean BTpathsum(BinNode root, int sum)
{
    if(root!=null)
    {
        if(root.value() == sum)
            return true;
        else
            return BTpathsum(root.left, sum - root.value()) || BTpathsum(root.right, sum - root.value());
    }
    else if(sum == 0)
        return true;
    else
        return false;
}

You didn't check to make sure the tree wasn't empty. If it has a height of zero and a sum of 0 you need to return true.

Tree, does the value equal sum (Boolean output)

1 Answers