Finding a seg fault in recursive code for inorder successor

Question

Hey guys I'm just practicing recursive code on a binary search tree. I'm getting a seg fault but I'm not sure where the problem is (probably something stupid staring me right in the face). I have other functions that are working fine like counting the number of nodes or counting the height of the tree. This function in particular is giving me trouble. I'm coding in c++.

//wrapper function
int table::in_order_successor()
{
    node * temp;
    temp = root;
    in_order_successor(root, temp);  
}

//Find the in-order successor
int table::in_order_successor(node * root, node * temp)
{
    if(root == NULL) return 0;

    if(root->right != NULL)
             if(root->data == temp->data)
                    in_order_successor(root, temp->right);

    in_order_successor(root, temp->left);

    return temp->data;
}

The idea I had was to get the function to go right once from the root and then continue left as far as possible. To get it to go right once I want to only go right if my root->data is equal to my temp->data (the data is just a randomly generated int).

Answer 1

For Seg fault, you should check whether temp is null, as you code might pass temp->right and temp->left to it, which might be null.

  if(temp == NULL) return 0; // add this check

But there is another problem in your code: you never reuse the return value. Then it will just iterate. Suppose you would like to return the data stored in the leaf node after your traversal, then the code could look like this:

//Find the in-order successor
int table::in_order_successor(node * root, node * temp) {
  if(root == NULL) return 0;
  if(temp == NULL) return 0; // add this check

  if(root->right != NULL) {
     // check by pointer instead of the data unless each
     // node->data is unique.  Otherwise unwanted moving
     // right will occur.
     if(root == temp) {           
       if (temp->right != null) {
         // use `return` here instead of plain function call to get
         // the update of the rest of the recursion.
         return in_order_successor(root, temp->right);
       }
     }
  }

  if (temp->left != null) {
    // if have left child, return what you will find in the next step
    return in_order_successor(root, temp->left); // use return here
  } else {
    // reach the left-most leaf after first steping right at root node.
    return temp->data;
  }
}

Answer 2

Also

 if(temp->left != NULL)
    in_order_successor(root, temp->left);

and

if(!temp-> left)
  return temp->data;