CODEWITHSUNDEEP
cpointersrecursionlinked-listbinary-search-tree
Rahul Arora
Rahul Arora

Reputation: 4523

Inserting into binary search tree using recursion in C

I was making a program to make a binary search tree which takes input from the user. I have deliberately shown two search functions in my code below.

Problem: The search function2 works correctly but the search function1 does not work correctly (when used after commenting the other each time). Why is it so?

I tried doing the dry run and building the recursion stack, which works fine as per me. But somehow I think the search function 1 is not able to make that linking in the linked list to insert the element. That is the reason I am not getting the right output when I try to do the inorder traversal

Any help will be really appreciated!

#include <stdio.h>
#include <stdlib.h>

struct node{
    int data;
    struct node *left;
    struct node *right;
};
struct node *root = NULL;

struct node *newNode(int data){
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

//SEARCH FUNCTION 1: this does not work correctly
void search(struct node *t,int data){
    if(t){
        if(data > t->data){
            search(t->right,data);
        }else{
            search(t->left,data);
        }
    }else{
        t = newNode(data);
    }
}

//SEARCH FUNCTION 2: this works fine and inserts the element correctly
void search(struct node *t, int data){
    if(data < t->data && t->left != NULL){
        search(t->left, data);
    }else if(data < t->data && t->left == NULL){
        t->left = newNode(data);
    }else if(data > t->data && t->right != NULL){
        search(t->right,data);
    }else{
        t->right = newNode(data);
    }
}

void insertNode(int data){
    if(!root){
        root = newNode(data);
        return;
    }
    search(root, data);
}

void inorder(struct node *t){
    if(t){
        if(t->left){
            inorder(t->left);   
        }
        printf("%d ->", t->data);
        if(t->right){
            inorder(t->right);  
        }
    }
}

int main(){
    int step, data;
    while(1){
        printf("1. Insert element\n");
        printf("2. Print tree\n");
        scanf("%d",&step);
        switch(step){
            case 1: printf("enter element to be inserted\n");
                scanf("%d",&data);
                insertNode(data);
                break;
            case 2:inorder(root); 
                printf("\n");
                break;
        }
    }
    return 0;
}

Upvotes: 1

Views: 1704

Answers (2)

gsamaras
gsamaras

Reputation: 73366

1st search function:

void search(struct node *t,int data){
    ...
    t = newNode(data);
}

but then in the 2nd search function you do:

void search(struct node *t, int data){
    ...
    t->right = newNode(data);
}

which will remember the assignment, while the first will not, since when you are going to recurse, the changes will be lost.

You see in the 2nd case, you are assign what newNode() returns to data member of a struct that is a pointer, while the struct is passed a pointer in this function. However, in the 1st case, you assign the result in a struct that is passed by one pointer only. If a double pointer would be used, things would be differently.

Upvotes: 1

kfx
kfx

Reputation: 8537

The problem is that the statement t = newNode(data) assigns to a local variable, so the result is lost immediately after returning from the function.

In this case one solution is double indirection, as you don't just want to modify the thing a pointer points to, but the pointer itself.

void search(struct node **pt,int data)
{
    struct node *t = *pt;
    if (t) {
        if (data > t->data) {
            search(&t->right,data);
        } else {
            search(&t->left,data);
        }
    } else {
        *pt = newNode(data);
    }
}

Upvotes: 1

Related Questions