Node Traversal & Seg Fault

[lasl0w]

Hello,
I'm doing a full traversal of a binary search tree structure looking for a node by a field that is not the sort key. If the node i'm looking for is the root node, no problem. If it's any other node then the function has a Seg Fault. Anyone know what is going on?

I'm pretty sure the problem is in my logic in what i'm returning from Find_Trav_Subtree, but cannot pinpoint it. gdb debugger gives me this, but i'm not sure if it helps.

Breakpoint 1, BSTClass::Print_Node (this=0x80537a4, NodePtr=0xb7f1e888) at bstree.cpp:227
227 {
(gdb) next
228 cout << NodePtr->Info.fields.size() << endl;
(gdb)
402
229 cout << setw(15) << NodePtr->Info.fields.at(0);
(gdb)

Program received signal SIGSEGV, Segmentation fault.
0x00cfa1e6 in std::operator<< , std::allocator > () from /usr/lib/libstdc++.so.6

Note - I can print using the same syntax (NodePtr->Info.fields.at(0)) from another function that just prints the entire tree and doesn't take a NodePtr as an argument.

// screen output
checking current info
checking current info
checking current info
about to return current
checking current info
checking current info
checking current info
Result returned successfully
about to print node
Segmentation fault

// Initial function calls
void Delete_by_ID( int id_choice )
{
   BSTNodePtr Result;

   FoundResult = NULL;
   //Find by ID
   //Result = reinterpret_cast <AVLNodePtr> (AVLTreeContacts.Find_Trav(id_choice));
   Result = AVLTreeContacts.Find_Trav(id_choice);

   cout << "Result returned successfully" << endl;
   if (Result == NULL)
        cout << "Result is Null" << endl;
   else {
        cout << "about to print node" << endl;
        AVLTreeContacts.Print_Node(Result);
   }
   //if user agrees, FreeNode
  
}



void BSTClass::Print_Node(BSTNodePtr NodePtr)
{
      cout << setw(15) << NodePtr->Info.fields.at(0);
      cout << setw(15) << NodePtr->Info.fields.at(1) << endl;
}


BSTNodePtr BSTClass::Find_Trav(int ID)
   {
   return Find_Trav_Subtree(Root, ID);
   }


BSTNodePtr BSTClass::Find_Trav_Subtree(BSTNodePtr Current, int ID)
   {
   if (Current != NULL) {
     cout << "checking current info" << endl;
     if (Current->Info.contact_id == ID){
            cout << "about to return current";
            return Current;
     }
     if (Current->Right) {
        Find_Trav_Subtree(Current->Right, ID);
     }
     if (Current->Left) {
        Find_Trav_Subtree(Current->Left, ID);
     }
   }

   if (Current == NULL)
        return NULL;
   }

[lasl0w]

I've changed Find_Trav_Subtree and added a return statement in front of the recursive call. I can now find nodes on the RIGHT side of the tree, but not the left.

I know i'm going to smack myself. Why is this not fully working?

BSTNodePtr BSTClass::Find_Trav_Subtree(BSTNodePtr Current, int ID)
   {
   if (Current != NULL) {
     cout << "checking current info" << endl;
     if (Current->Info.contact_id == ID){
            cout << "about to return current" << endl;
            return Current;
     }
     if (Current->Right) {
        return Find_Trav_Subtree(Current->Right, ID);
     }
     if (Current->Left) {
        return Find_Trav_Subtree(Current->Left, ID);
     }
   }

   if (Current == NULL)
        return NULL;
   }

[StuXYZ]

Obviously, it would be a lot easier to look at this if you had posted all the code.

However: Find_Trav_Subtree looks very strange [to me].

You see it calls the right branch if (current->Right) AND thenalways returns Find_Trav_Subtree from the right branch REGARDSLESS of it returning a NULL. I would have expected to see something like this:

BSTNodePtr Result(0);
// Note only return from right if a valid result is found:
if ( Current->Right && (Result = Find_Trav_SubTree(Current->Right,ID)) )
   return Result;
return ( Current->Left) ? Find_Trav_SubTree(Current->Left,ID) : 0;

There are many ways to do this.

Hope that helps, if not please post the full BSTClass so we can also compile and debug it.

[lasl0w]

Thanks - that took care of it. I've never been exposed to that ? and : syntax. I'll have to read up and play with it. Appreciate the help!