Code doesn't compile becasue of "not all paths return value" even though logically they do

Here is my Search method in the BTree class:

public bool Search(string val)
    {
        if (String.Compare(Value, val, false) == 0)
            return true;

        if (String.Compare(Value, val, false) < 0)
        {
            if (RightChild != null)
                RightChild.Search(val);
            else return false;
        }
        else
        {
            if (LeftChild != null)
                LeftChild.Search(val);
            else return false;
        }
    }

This code dosen't compile, since not all paths return value (all my returns are conditioned), even though logically they do.. I cant figure out how to solve this basic problem.. Maybe my entire approach is wrong?