Inserting into binary search tree using recursion in C

Question

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;
}

Where is newNode(data); assigned if t is NULL in function 1? — David C. Rankin
– David C. Rankin, Commented May 9, 2017 at 17:11
@DavidC.Rankin in the else part of it. That is what I want to understand. Is recursion only helping to traverse the linked list and insertion has to be explicitly stated? — Rahul Arora
– Rahul Arora, Commented May 9, 2017 at 17:13
depends if data value is greater or lesser. If greater it will call the function again with right value of node and if less it will call it with left value of the node — Rahul Arora
– Rahul Arora, Commented May 9, 2017 at 17:15

kfx · Accepted Answer · 2017-05-09 17:12:13Z

1

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);
    }
}

answered May 9, 2017 at 17:12

kfx

8,5773 gold badges33 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Rahul Arora Over a year ago

how is recursion able to remember t->right then? That is also coming from a local variable only. This is the part that is confusing me.

kfx Over a year ago

@RahulArora because the address of t->right is already reachable from the root of the tree. The address of the function parameter t is not on the other case, as this t ceases to exist once the function returns.

gsamaras · Accepted Answer · 2017-05-09 17:26:13Z

1

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.

edited May 9, 2017 at 17:26

answered May 9, 2017 at 17:13

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

2 Comments

Rahul Arora Over a year ago

But how is the second function able to remember? In second function also, right node of local variable struct node *t is assigned a value. How is recursion able to associate the right node of the node from the local variable struct node *t?

gsamaras Over a year ago

Good question @RahulArora, I updated my answer, hope this helps. +1 for your good (initial) question.

Collectives™ on Stack Overflow

Inserting into binary search tree using recursion in C

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related