CODEWITHSUNDEEP
javarecursionbinary-search-tree
User 965
User 965

Reputation: 189

Java BST recursion variable setting

I have a normal binary search tree implemented with a string value for data, and right and left nodes. The tree works fine but I am having trouble with my rankOf function. I use recursion to find the nodes and the method is successful when the element exists, but when a value not present is does not work and I can't figure out how to set a boolean within to help with this. Here is the code:

private int rankOf(String s, Node n){
    if (n != null){

        //check root
        if (s.compareTo(n.value) == 0){
            if (n.left != null){
                return size(n.left);
            }
            return 0;
        }
        // only worry about left tree, easy
        if (s.compareTo(n.value) < 0){
            return rankOf(s, n.left);
        } else {
            // must count entire left tree plus root node
            return rankOf(s, n.right) + size(n.left) + 1;
        }

    }
    //null or not found
    return 0;
}

When root is equal to the value I know the element is in the tree so something should go in there but unsure how to handle this.

Upvotes: 0

Views: 40

Answers (1)

Schidu Luca
Schidu Luca

Reputation: 3947

This checking is useless:

if (n.left != null){
     return size(n.left);
}

Anyway, you can do something like this:

static int rankOf(String s, Node root) {
    if(root == null) {
        return -1;
    }

    if(root.value.equals(s)) {
        return size(root);
    }

    int result;
    if(s.compareTo(root.value) > 0) {
        result = rankOf(s, root.right);
    } else {
        result = rankOf(s, root.left);
    }
    return result;
}

And your size() method:

static int size(Node root) {
    if(root == null) return 0;
    return size(root.left) + size(root.right) + 1;
}

In case the String is not found, -1 will be returned.

Upvotes: 1

Related Questions