0

After trying to call a simple program to test my method for finding the 1st smaller node than the one given as a parameter:

BinaryTreeMap <int, int> m;
m[5] = 5;
m[3] = 3;
m[8] = 8;
m[1] = 1;
m[2] = 2;
m[6] = 6;
cout << m.firstSmaller(5) << " ";
cout<< m.firstSmaller(6);
cout << " " << m.firstSmaller(3) << " ";
cout << m.firstSmaller(12);

...my program just collapses, no errors, nothing. I pressume I am making some kind of an infinite loop by not exiting the recursive function correctly. But I don't know where, since when I try go by my method on a piece of paper, I get the correct result.

Here is the method:

template <typename TipKey,typename TipValue>
TypeValue BinaryTreeMap<TipKey,TipValue>::firstSmaller(TypeKey key)
{
BSNode *pom = functionforFirstSmaller(root, key);
if(pom == 0) throw "There is no key smaller than the given one!";
return pom->value;
}

And the functionforFirstSmaller:

BSNode* functionforFirstSmaller(BSNode *c, TypeKey k)
{
    if(c->left == 0 && c->right == 0) return c;
    if(c == 0) return 0;
    if(c->key >= k) return functionforFirstSmaller(c->left, k);
    BSNode *cvor = functionforFirstSmaller(c->right, k);
    //if(cvor == 0) return 0;
    return cvor;
}

I don't understand why it's crashing. If you guys could help me to understand, I would really appreciate it, since it would help me in my further on programming. Sorry if it's not good explained, getting used to the English vocabulary in C++(not my native language).

5
  • What is root in firstSmaller()? Dec 27, 2013 at 16:11
  • Root is the root of the whole binary tree. If the key I'm looking for smaller than it, it should be in the left SubTree.
    – Emir
    Dec 27, 2013 at 16:13
  • 1
    try printing some output inside your recursive function. It will help you identify when it fails Dec 27, 2013 at 16:14
  • Is it possible that c == 0 ? Since it's a pointer it looks weird to me. Same for pom == 0
    – Yabada
    Dec 27, 2013 at 16:14
  • It seems that when c=3 and then tries to call functionforFirstSmaller(3->right, k), 3->right is actually null , but still, didn't I take care of that problem in those first 2 ifs ?
    – Emir
    Dec 27, 2013 at 16:26

1 Answer 1

0

It seems that you have inverted two lines of code. try:

BSNode* functionforFirstSmaller(BSNode *c, TypeKey k)
{
    if (c == 0) return 0;
    if (c->left == 0 && c->right == 0) return c;
    if (c->key >= k) return functionforFirstSmaller(c->left, k);
    BSNode *cvor = functionforFirstSmaller(c->right, k);
    return cvor;
}
1
  • Still crashing, but thank you for the answer. I believe I'm making some mistakes by trying to get to null pointers. That must be it. Will try to fix it now.
    – Emir
    Dec 27, 2013 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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