Given an element, returning the inorder rank of it an in a binary search tree with only two parameters

Question

I have a solution here, but I'm not too fond of it because I feel like it can be done better.

template <typename Comparable>
bool AugmentedBinarySearchTree<Comparable>::Rank(const Comparable& x, BinaryNode* t, int* nodesVisited) const {
  if (t == NULL) {
    return false;
  }
  if (Rank(x, t->m_left, nodesVisited)) {
    return true;
  }
  *nodesVisited += 1;
  if (t->m_element == x) {
    return true;
  }
  return Rank(x, t->m_right, nodesVisited);
}

My biggest stumbling block was finding way to both confirm the node actually existed and also returning its rank.

I started with this method signature

int BinarySearchTree<Comparable>::Rank(const Comparable& x, BinaryNode* t) const {

but in the end I had to make the method return a bool and add an extra parameter to keep track to where the program was in the traversal.

Is there any way to do this without the nodesVisited parameter?

Answer 1

I'd recommend the following approach. Split up Rank into a public-facing member function and a private-facing member function. The private one's signature is:

template <typename Value>
std::pair<bool, int> RankImpl(BinaryNode* tree, const Value& value);

The public one is:

template <typename Value>
boost::optional<int> Rank(BinaryNode* tree, const Value& value);

(Secondarily, I flipped the order of your arguments, provided better names for them, and am not limiting the value we're looking for to be a Comparable. Rather, anything that is equality-comparable to Comparable should suffice).

The idea of using boost::optional is that it, as a return type, already encompasses what you want in a single type - it tells you if there is or isn't a value (i.e. was value found or not) and if there is a value, what it is (i.e. its rank). We however privately still need a value even in the false case, hence the pair helper function.

Altogether:

template <typename Value>
boost::optional<int> Rank(BinaryNode* tree, const Value& value)
{
    auto pr = RankImpl(tree, value);
    if (pr.first) {
        return pr.second;
    }
    else {
        return boost::none;
    }
}

template <typename Value>
std::pair<bool, int> RankImpl(BinaryNode* tree, const Value& value)
{
    if (!tree) {
        return {false, 0};
    }

    auto left = RankImpl(tree->left, value);
    if (left.first) {
        return left;
    }
    else if (tree->m_element == value) {
        return {true, left.second + 1};
    }        
    else {
        auto right = RankImpl(tree->right, value);
        return {right.first, left.second + 1 + right.second};
    }
}