Searching for a binary tree for a vehicle with a given name

Question

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; 
 else 
 return n.hasRight() ? find(name, n.right()) : null;
}

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

• Simon Forsberg: 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.

Answer 1

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.