Binary trees FindParent method doesn't seem to work

Question

Here is my BNode class

class BNode
{
    public int number;
    public BNode left;
    public BNode right;
    public BNode(int number)
    {
        this.number = number;
    }
}

And here is my implementation of FindParent method in BTree class

 public BNode FindParent(BNode BNode, BNode searchNode)
    {
        if (searchNode.left == BNode || searchNode.right == BNode)
        {
            return searchNode;
        }
        if (searchNode.left != null)
        {
            return (FindParent(BNode, searchNode.left));
        }
        if (searchNode.right != null)
        {
            return (FindParent(BNode, searchNode.right));
        }
        return null;
    }

Here is how i call it

    BNode bnodeFound = btree.Find(18);
    BNode bparent = btree.FindParent(bnodeFound, btree.rootNode);

It returns null always, except when the number is the first root from the trees root. What i also found trough debugging is that it goes to the left-most root, checks that it has no right root and then returns null. Have tried to figure out this, but to no success. I use similiar way to find a number in the tree, and that works for finding 18.

Answer 1

When you call FindParent() recursively each time for the left node (when it is not null), you are returning it directly which means the FindParent() for the right node will never be called.

// Assume we run this for the root node
if (searchNode.left != null)
{
    // If left node is not null, then it tries to find in left subtree only
    // Since it returns directly, whether found or not-found it WILL NOT
    // search in right sub-tree
    return (FindParent(BNode, searchNode.left));
}

// Unreachable code if left is not NULL
if (searchNode.right != null)
{
    return (FindParent(BNode, searchNode.right));
}

To fix you can remove the return statement and instead check if it is still not found.

if (searchNode.left != null)
{
    var found = (FindParent(BNode, searchNode.left));
    // Return if found, else continue to check in right
    if (found != null) return found;
}

// Checks in right sub-tree if not found in left subtree
if (searchNode.right != null)
{
    // While checking in right sub-tree, then return irrespective of whether
    // it was found or not found, since there aren't any more places to check
    return (FindParent(BNode, searchNode.right));
}