Finding the number of nodes with int data greater than x in a binary search tree

I’m trying to recursively find the number of nodes that have int data greater than than a given int. This is being done on a binary search tree, so it makes things a bit easier in terms of finding the amount. However, my solution seems to be one-off on all of the tests I’ve run and I can’t figure out why, see below:

private int numGreaterThan(Node r,int d) {
    if(r.data > d) return 0;
    return 1 + numGreaterThan(r.right, d);
}

I know I could just search the whole tree, but that would be inefficient and not really make use of the binary search tree’s structure. Am I possibly overlooking something here? My thought process here was to just go right, as that is where the largest values are, but perhaps this is flawed.

Answer

Some issues:

• Your code should check whether r is null before anything else.
• You can only return 0 when you have arrived at a null.
• Returning 0 when r.data > d is certainly wrong, as that node itself should be counted, and all the nodes in the right subtree
• Your code never looks in the left subtree. When r.data > d there can also be nodes in the left subtree that should be counted.

Here is a correction:

    private int numGreaterThan(Node r, int d) {
        if (r == null) return 0;
        int count = numGreaterThan(r.right, d);
        if (d < r.data) count += 1 + numGreaterThan(r.left, d);
        return count;
    }

Or using the ternary operator:

    private static int numGreaterThan(Node r, int d) {
        return r == null ? 0
             : numGreaterThan(r.right, d) +
                (d < r.data ? 1 + numGreaterThan(r.left, d) : 0);
    }