Given an element, returning the inorder rank of it an in a binary search tree with only two parameters I have a solution here, but I'm not too fond of it because I feel like it can be done better.

template &lt;typename Comparable&gt;
bool AugmentedBinarySearchTree&lt;Comparable&gt;::Rank(const Comparable&amp; x, BinaryNode* t, int* nodesVisited) const {
  if (t == NULL) {
    return false;
  }
  if (Rank(x, t-&gt;m_left, nodesVisited)) {
    return true;
  }
  *nodesVisited += 1;
  if (t-&gt;m_element == x) {
    return true;
  }
  return Rank(x, t-&gt;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&lt;Comparable&gt;::Rank(const Comparable&amp; 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?
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 &lt;typename Value&gt;
std::pair&lt;bool, int&gt; RankImpl(BinaryNode* tree, const Value&amp; value);


The public one is:

template &lt;typename Value&gt;
boost::optional&lt;int&gt; Rank(BinaryNode* tree, const Value&amp; 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 &lt;typename Value&gt;
boost::optional&lt;int&gt; Rank(BinaryNode* tree, const Value&amp; value)
{
    auto pr = RankImpl(tree, value);
    if (pr.first) {
        return pr.second;
    }
    else {
        return boost::none;
    }
}

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

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