CODEWITHSUNDEEP
c++algorithmrecursionbinary-search-tree
Zafar
Zafar

Reputation: 1201

Rank of a node in BST using in-order traversal in c++

I have been chasing my tail to find the rank of the node in a BST. I`ve got void function which accepts an element and using recursion finds a rank of the node.
I inserted nodes in the following order: 12, 3, 7, 4, 11, 17, 15, 9. My problem is that whenever I found a match the recursion does not stop! Here is my algorithm: 

template <class Comparable>
void AugmentedBinarySearchTree<Comparable>::
Rank(const Comparable & x, BinaryNode<Comparable> *t, int *nodesVisited) const
{  

    // x is the element I am looking for
    // t is the root
    if (t->left != NULL)
    {

    Rank(x, t->left, nodesVisited);                         
    if(t->left->element == x)
        return; 
    }
    cout << "element " << t->element << ", x " << x << ", nodesVisited "<< *nodesVisited << endl;
    if (x == t->element) 
    {               

        cout << "found the node " << endl;
        return ; // exiting the recursion, nodesVisited will be the rank 
                // nodesVisited starts counting from 1
    }

    ++(*nodesVisited); // incrementing the count

    if (t->right != NULL)
    {       
        Rank(x, t->right, nodesVisited);    
    }
}

It works when I do Rank(3), but when I do Rank(4) recursion does not stop and I am getting different result:

element 3, x 4, nodesVisited 1
element 4, x 4, nodesVisited 2
found the node 
element 12, x 4, nodesVisited 2
element 15, x 4, nodesVisited 3
element 17, x 4, nodesVisited 4
RANK: 5

How do I stop the recursion whenever I found a match?

Upvotes: 0

Views: 1618

Answers (1)

molbdnilo
molbdnilo

Reputation: 66371

You terminate the recursion if you found the item in the left child node.
You need to stop if it was found in the left subtree.

Something like this might do it (I amended it to return the rank, as you said you intend to).
In my opinion, using a "null" base case often leads to simpler tree recursions.
(Thoroughly untested code, by the way. There are probably bugs.)

int Rank(const Comparable & x, const BinaryNode<Comparable> *t) const
{
    int rank = 0;
    return FindRank(x, t, &rank) ? rank : -1;
}

// Returns 'true' if and only if the node was found in 't'.
bool FindRank(const Comparable & x, const BinaryNode<Comparable> *t, int* nodesVisited) const
{
    if (t == nullptr)
    {
        return false;
    }

    if (FindRank(x, t->left, nodesVisited))
    {
        return true;
    }

    *nodesVisited += 1;
    return t->element == x || FindRank(x, t->right, nodesVisited);
}

Upvotes: 1

Related Questions