Code review: How could I simplify this simple method?

Question

I have the following simple method for doing a complete search of a binary tree. I can definitely tell it can be simplified, but it's not coming to me.

bool Node::lookup(int d)
{
    if (data==d)
    {
        return true;
    }
    else
    {
        if (left != NULL && right != NULL)
        {
            return left->lookup(d) && right->lookup(d);
        }
        else if (left != NULL)
        {
            return left->lookup(d);
        }
        else if (right != NULL)
        {
            return right->lookup(d);
        }
        else
        {
            return false;
        }
    }
}

Answer 1

bool Node::lookup(int d)
{
    return (data==d)
        || ((NULL != left) && left->lookup(d))
        || ((NULL != right) && right->lookup(d));
}

Takes advantage of short-circuit behaviour of && and ||.

Note that this isn't exactly equivalent to your code, but I imagine that this is probably the behaviour you actually want. (Your original code returns false is both children exist and d isn't in both of them.)

Answer 2

It cannot be made significantly faster. However, I'd write it as

bool Node::lookup(int d){
    if (!this) // a little bit unorthodox, but much more elegant that testing before call
        return false;
    return (data == d) || left->lookup(d) || right->lookup(d);
}

EDIT: It seems that no one likes this approach. But why? Except for the case of virtual functions it provides better encapsulation than the standard one:

Node* tree; 
if (tree->lookup(i)) // we encapsulate in the Node class the information that an empty tree must return false
    printf("found!\n");

Node* tree; 
if (tree && tree->lookup(i)) // we have to know in the outside that a NULL tree shall return false
    printf("found!\n");

The only way it could produce UB is when the compiler will consider that this cannot be NULL and will skip the test. This will not happen because there is quite enough code in the wild that use this kind of checking. Also, in plain C it's common practice.

Answer 3

You could get rid of the nested ifs and else ifs

bool Node::lookup(int d)
{
    if (data==d)
        return true;
    if (left != NULL && right != NULL)
        return left->lookup(d) && right->lookup(d);
    if (left != NULL)
        return left->lookup(d);
    if (right != NULL)
        return right->lookup(d);
    return false;
}

Answer 4

If you want a terse version of the code in the question, you can do this:

bool Node::lookup(int d) 
{ 
    return 
        (data==d) || 
        (
            (right || left) &&
            (!left || left->lookup(d)) &&
            (!right || right->lookup(d))
        ); 
} 

But I suspect you want lookup to return true if d matches in either left or right, not if it matches in both left and right

Answer 5

Ternary operator shortens things nicely:

bool Node::lookup(int d)
{
  if (data==d)
    return true;

  if (left == right)
    return left == null ? false : left->lookup(d) && right->lookup(d);   
  return left == null ? right->lookup(d) : left->lookup(d);
}

Answer 6

bool Node::lookup(int d)
{
    return (data == d)
       || (left && left->lookup(d))
       || (right && right->lookup(d));    
}

I'm making an assumption that you have a logic error in your originial, since it requires that if the left and right child are non-null that the target be found in both branches.