C Programming Binary Tree Insertion Recursively (Not Binary Search Tree)

Question

This is my code here. I want to insert the items recursively into the binary tree. It's not a binary search tree (left child need not be < parent or right child need not be > parent).

It's simply a binary tree where there can be at most two children for each node. When I execute the traversal, it just prints out the starting node endlessly in an infinite loop (5-> 5-> 5->....). Please help me out.

I've searched through Stack Overflow and nothing is based on this. Most are binary search trees. I'm sorry if this is a bad question.

struct node {
    int info;
    struct node* left;
    struct node* right;
}*temp, *ptr, *prev;

struct node *root, *start=NULL;

void insert(struct node*);
void inorder(struct node*);

void insert(struct node* ptr)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;     //ptr is set as new node
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(ptr==start)
            insert(start->left); //start->left will be the new 'ptr' in the next insertion scenario
        else
            insert(ptr->left);  //same principle as above
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        if(start==ptr)
            insert(start->left);
        else
            insert(ptr->right);
    }

}

void inorder(struct node* ptr)
{
    while(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

void main(){
    int ch;
    do{
        puts("1. Insert 2.Traverse 3.Exit");
        scanf("%d",&ch);
        switch(ch){
            case 1:
                puts("Enter root node");
                root=(struct node *)malloc(sizeof(struct node));
                root->left=NULL;
                root->right=NULL;
                scanf("%d", &root->info);
                insert(root);
                break;
            case 2:
                inorder(start);
        }
    }while(ch!=3);
}

Thanks in advance, guys.

Your traversal function looks ok, but your insertion code is all over the place. I would suggest two things : 1. stop with the globals. This is generally bad practice, especially when dealing with chained lists. 2. Use a function (or functions) to manipulate your tree and add/insert nodes. — Eregrith
– Eregrith, Commented Apr 10, 2015 at 12:50
If you have never used a debugger before, this looks like a great opportunity to learn. See thegeekstuff.com/2010/03/debug-c-program-using-gdb if you have gdb available on your system. — ericzundel
– ericzundel, Commented Apr 10, 2015 at 13:05
@Eregrith The traversal function does not look ok — it loops forever if ptr != NULL. — CiaPan
– CiaPan, Commented Apr 10, 2015 at 18:00
@CiaPan wow indeed sorry I think I need to sleep more >_<. Did not see the while — Eregrith
– Eregrith, Commented Apr 12, 2015 at 9:37

huxley · Accepted Answer · 2015-04-19 05:08:37Z

3

your traversal create infinite loop, you should change the while to if

void inorder(struct node* ptr)
{
    if (ptr != NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

in insert(struct node* ptr) when you do ptr=temp; it's only changing ptr inside the function scope, so actually you never assign left and right nodes for the root

edited Apr 19, 2015 at 5:08

answered Apr 10, 2015 at 12:55

huxley

3074 silver badges9 bronze badges

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

1 Comment

akkhil Over a year ago

Thanks for pointing out the traversal function's mistake. Also about the insertion function, what you said makes sense. What would be an apt solution?

CiaPan · Accepted Answer · 2015-04-10 13:20:13Z

0

Try this way of adding nodes:

struct node *createTree()
{
    struct node *node;
    int resp;

    node=malloc(sizeof(struct node)); //new node created
    node->left=NULL;
    node->right=NULL;
    puts("Enter value");
    scanf("%d", &node->info);

    printf("Does %d have a left node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->left = createTree();

    printf("Does %d have a right node? (1/0)\n", node->info);
    scanf("%d", &resp);
    if(resp==1)
        node->right = createTree();

    return node;
}

then in main() do:

root = createTree();

Note the resp variable is of type int if you scan it with "%d" format. For type char you should use format "%c".

answered Apr 10, 2015 at 13:20

CiaPan

9,5802 gold badges23 silver badges38 bronze badges

Comments

akkhil · Accepted Answer · 2015-04-10 19:58:21Z

I have found the solution for this. Sorry for wasting your time. The problem with my code was:

1) The while instead of if in the traversal function 2) Secondly, when I pass the argument ptr, it doesn't know where to link that ptr to. All I'd been doing was ptr=temp. It must link to the previous node's left/right, right?

@huxley's explanation along the lines of function scope was wrong. It must point to the same object - that's why we use pointers, right? However, it rang a bell in my head. So here's the solution below:

void insert(struct node* ptr, int side)
{
    int ch;

    if(start==NULL)  // if start is null, new node is made as start node.
        start=ptr;
    else
    {
        temp=(struct node*)malloc(sizeof(struct node)); //new node created
        temp->left=NULL;
        temp->right=NULL;
        puts("Enter value");
        scanf("%d", &temp->info);
        ptr=temp;
        if(side==1)
            prev->left=ptr;
        else
            prev->right=ptr;
    }

    printf("Does %d have a left node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->left, 1);
    }

    printf("Does %d have a right node? (1/0)\n", ptr->info);
    scanf("%d", &ch);
    if(ch==1)
    {
        prev=ptr;
        insert(ptr->right, 2);
    }

}

void inorder(struct node* ptr)
{
    if(ptr!=NULL)
    {
        inorder(ptr->left);
        printf("%d -> ", ptr->info);
        inorder(ptr->right);
    }
}

I explained it detailedly because there's not a proper insertion code for binary tree using recursion. I hope everyone understands.

Thanks everyone who helped.

Cheers, Akhil

Collectives™ on Stack Overflow

C Programming Binary Tree Insertion Recursively (Not Binary Search Tree)

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related