BST insertion in c using recursion

Question

I'm new to c but have programmed in other languages. I have this piece of code for BST insertion:

struct tnode {
  int data;
  struct tnode* left;
  struct tnode* right;
};

struct tnode* addnode(struct tnode* root, int data) {
    if (root == NULL) return talloc(data);
    else if (data < root->data) root->left = addnode(root->left, data);
    else root->right = addnode(root->right, data);
}

The code works perfectly well but it's driving me crazy trying to understand how it works. I feel like it shouldn't return correctly but I've tested it extensively and it works. My gripe is when you call addnode with a root whose value isn't NULL it recursively calls addnode which returns a new tnode to root->left or root->right. This is fine. However, after the recursive call has returned the function should resume execution from that point in the original call. Then it should resume after the if-else clause. After that clause there is no return. How the hell is it returning correctly when I add multiple items?

I was trying things out and added a puts("hello"); after the if-else clause and that messed up the entire thing and gave me a segmentation fault: 11 (whatever that means).

You should be getting compilation warnings because there is no return for the else if or else branches of the function. You should probably have return root; before the }. — Jonathan Leffler

Unknown Unknown · Accepted Answer · 2017-05-05T03:05:45

You are absolutely right. The function you have is missing a return call after the else statement which would definitely give you confusion. Try using the following function:

struct tnode* addnode(struct tnode* root, int data) {
    if (root == NULL) return talloc(data);
    else if (data < root->data) root->left = addnode(root->left, data);
    else root->right = addnode(root->right, data);
    return root;
}

Let me know if this helps. Happy programming!

BST insertion in c using recursion

1 Answers