2
\$\begingroup\$

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?

\$\endgroup\$
7
  • \$\begingroup\$ Just to be clear, you have to return false in case you can't find x at all? Why not just return a negative number in that case? Then you can keep an int return type, no? \$\endgroup\$ – sunny Oct 29 '15 at 19:56
  • \$\begingroup\$ @sunny Yeah but it's basically the same thing as a bool at that point anyways isn't it? Negative = false and Positive = true. If I tried to store that state in nodesVisited, which I did try, it'll screw up the value I need returned. \$\endgroup\$ – m0meni Oct 29 '15 at 20:00
  • \$\begingroup\$ Maybe I'm misunderstanding you. I thought your desire was to return the int count rather than the bool true or false? can't you do that once you return a negative value for x in the case of a null node? It seems like nothing else would need to change. \$\endgroup\$ – sunny Oct 29 '15 at 20:09
  • \$\begingroup\$ Right, but that would still require the third parameter. I guess my real question then, and I'll edit this, is it possible to achieve this with only two parameters (without nodesVisited)? \$\endgroup\$ – m0meni Oct 29 '15 at 20:17
  • 1
    \$\begingroup\$ @AR7 Don't worry about including templates. No code size/performance penalties. BTW, idiomatic Python would raise a KeyError exception. \$\endgroup\$ – vnp Oct 29 '15 at 20:43
1
\$\begingroup\$

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};
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ As I've gotten more into programming I've heard the NULL isn't a great idea, so is boost::optional the way around dealing with NULL? Also any reason you prefer auto over the actual type in this case? \$\endgroup\$ – m0meni Oct 29 '15 at 20:55
  • \$\begingroup\$ @AR7 I don't know what NULL has to do with anything. There's no NULL to deal with? auto is just less to type and will definitely give me the correct type. \$\endgroup\$ – Barry Oct 29 '15 at 21:06
  • \$\begingroup\$ I guess I was making a connection to something that wasn't here. Thank you for your help! \$\endgroup\$ – m0meni Oct 29 '15 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.