I'm searching my binary search tree of Vehicle objects and I'm just wondering whether there would be much point, if it's best practice to search to see if a node has a left/right child first like so:

return n.hasLeft() ? find(name, n.left()) : null;

Or just go with the following, since it will return null if it doesn't exist anyway:

return find(name, n.left());

Here's the code for the whole method:

protected Vehicle find(String name, Node n)
    if (n == null) return null;

    int order = name.compareTo(n.getVehicleName());

    if (order == 0)
        return n.getVehicle();  
    else if (order < 0)
        return n.hasLeft() ? find(name, n.left()) : null;       
        return n.hasRight() ? find(name, n.right()) : null;

Would checking first be more efficient since it saves an extra recursive call being made?

  • \$\begingroup\$ If you want to know if there is a performance difference is this detail, I'd recommend finding a benchmarking tool and benchmark it. However, you might want to consider other aspects of it too. Either way, I would recommend to choose one way and be happy with it. \$\endgroup\$ – Simon Forsberg Nov 25 '17 at 18:55

The if (n == null) return null;statement in find() is the only base case that you need. Checking for n.hasLeft() is redundant, and it doesn't even reduce the total number of function calls, since n.hasLeft() is itself a function call.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.