C- Binary Search Tree

Question

I am trying to build a a binary search tree. But I am not getting the correct output when performing the different traversals.

typedef struct binary_search_tree{
    struct binary_search_tree *lchild;
    int data;
    struct binary_search_tree *rchild;
}bst_t;

#define ALLOCATE (bst_t*)malloc(sizeof(bst_t))

Here is the insert function:

void insert(bst_t *ptr,int data){
    if( ptr->data < data){
        if ( ptr->lchild == NULL ){
            ptr->lchild = ALLOCATE;
            ptr->lchild->data = data;
            return;
        }else
            insert(ptr->lchild,data);
    }else{
        if ( ptr->rchild == NULL ){
            ptr->rchild = ALLOCATE;
            ptr->rchild->data = data;
            return;
        }else
            insert(ptr->rchild,data);
    }
}

Is this function correct? I am sending the address of root while calling that function.

You have overlooked that `malloc` does not initialise the memory. So the pointers in the new node are not `NULL` but indeterminate. — Weather Vane, Jun 17 '16 at 18:40
After `ptr->lchild->data = data;` you have missed out `ptr->lchild->lchild = NULL; ptr->lchild->rchild = NULL;` and similar in the other branch. — Weather Vane, Jun 17 '16 at 18:44
I did! But same thing.. I think as the structure is declared in static main memory so it is having initial values as `NULL` — Parnab Sanyal, Jun 17 '16 at 18:50
No, the structure memory is dynamically obtained except possibly the root node. — Weather Vane, Jun 17 '16 at 18:51
[Here is the code.. Please tell me what else in needed?](https://drive.google.com/file/d/0BwdBHI1607sZek1LS19qMTJ3NVE/view?usp=sharing) — Parnab Sanyal, Jun 17 '16 at 18:54
That code clearly shows the lines you have omitted: `ptr->lchild->lchild = ptr->lchild->rchild = NULL;` and similar in the other branch. — Weather Vane, Jun 17 '16 at 18:55
I copy pasted, compiled and ran the code you linked. It crashed. — Weather Vane, Jun 17 '16 at 19:00
[But it is running well. gcc 5.3.1](https://drive.google.com/file/d/0BwdBHI1607sZNWItWVpvYU9vMW8/view?usp=sharing) — Parnab Sanyal, Jun 17 '16 at 19:05
*"But I am not getting the correct output"* and *"But it is running well"* are contradictory, and vague. The only thing wrong with the code you posted is that you didn't properly initialize the structure after allocating it. Failure to properly initialize the structure leads to [undefined behavior](https://stackoverflow.com/a/33797630/3386109), which means that anything can happen (including sort of working). — user3386109, Jun 17 '16 at 19:11
I have said "But it is running well" after Weather Vane said that it crashed on his machine. Code is running .. But the correct output is not being produced. — Parnab Sanyal, Jun 17 '16 at 19:14
@ParnabSanyal Ok, but that's the kind of symptom that can be caused by *undefined behavior*. — user3386109, Jun 17 '16 at 19:16
When programming a data structure such as tree, always start with the empty case. Does your function work with an empty tree? Don't think so. One might say that the empty case is handled elsewhere, or that the trees are never empty, but this always leads to a trouble one way or another. — n. m. could be an AI, Nov 21 '19 at 11:52

user3386109 · Answer 1 · 2016-06-17T19:02:55.610

1

The problem is the ALLOCATE macro. It doesn't do nearly enough to properly allocate and initialize a new node. I suggest creating a newNode function that allocates memory for the node, and then initializes all of the members of the structure, like this

bst_t *newNode(int data)
{
    // allocation and error checking
    bst_t *node = malloc(sizeof(bst_t));
    if ( node == NULL )
    {
        fprintf(stderr, "out of memory\n");
        exit( 1 );
    }

    // initialize the members of the structure
    node->lchild = NULL;
    node->data = data;
    node->rchild = NULL;

    return node;
}

Then the insert function can be simplified to this

void insert(bst_t *ptr,int data)
{
    if( ptr->data < data){
        if ( ptr->lchild == NULL )
            ptr->lchild = newNode(data);
        else
            insert(ptr->lchild,data);
    }else{
        if ( ptr->rchild == NULL )
            ptr->rchild = newNode(data);
        else
            insert(ptr->rchild,data);
    }
}

edited Jun 17 '16 at 19:02

answered Jun 17 '16 at 18:57

user3386109

34,287
7
49
68

Sir, here is the code.. I think I have done what you have instructed but alas ! still not working.. thanks for your time though. If you find anything please tell me. [Code](https://drive.google.com/file/d/0BwdBHI1607sZMkFUdTF3NjlyNEU/view?usp=sharing) – Parnab Sanyal Jun 17 '16 at 19:18
1

@ParnabSanyal If you have other problems in the code, then you'll need to start a new question. In that question, be sure to provide a [Minimal, Complete, and Verifiable Example](https://stackoverflow.com/help/mcve). And also provide sample input, as well as expected and actual output. – user3386109 Jun 17 '16 at 19:22
Well! I have used the same ALLOCATE macro to my other binary-tree program. It is working fine and producing correct output. So, I think macro is not the problem here. Okay I will post this in a new thread. – Parnab Sanyal Jun 17 '16 at 19:32

C- Binary Search Tree

1 Answers1