Binary search tree of strings implementation in c++

Question

I have written a program that inserts integer values into binary search tree. It seems to work fine but when I modify the same to accept a character array instead of an integer, I get unexpected results. Here is my complete code:

struct Node{
char data[50];
struct Node* right;
struct Node* left;
};

typedef struct Node* NODE;

NODE createNode(char data[]){
    NODE newNode = (NODE) malloc (sizeof(struct Node));

if(!newNode){
    cout<<"Not enough memory"<<endl;
    exit(-1);
}
newNode->left = NULL;
newNode->right = NULL;
strcpy(newNode->data,data);
return (newNode);
}

void insertNode(NODE* head,char data[]){

    NODE newNode = createNode(data);
    NODE hold_the_head = *head;
    if(*head == NULL){
        *head = newNode;
        (*head)->right = NULL;
        (*head)->left = NULL;
        return;
    }

    while(1){
        if((newNode->data>(*head)->data)&&((*head)->right==       NULL)){
            (*head)->right = newNode;
            *head = hold_the_head;
            return;
        }
        else if( newNode->data > (*head)->data ){
            (*head) = (*head)->right;
        }

        else if( (newNode->data < (*head)->data) && ( (*head)->left ==   NULL ) ){
            (*head)->left = newNode;
            *head = hold_the_head;
            return;
        }
        else if( newNode->data < (*head)->data ){
            (*head) = (*head)->left;
        }
    }
}

void inOrderTraversal(NODE node){

    if(node == NULL)
       return;
    inOrderTraversal(node->left);
    cout<<node->data<<"\t";
    inOrderTraversal(node->right);
}

int main(){

    NODE head = NULL;
    insertNode(&head,"karan");
    insertNode(&head,"sameer");
    insertNode(&head,"palak");
    insertNode(&head,"jagdish");
    insertNode(&head,"naman");
    insertNode(&head,"umang");
    insertNode(&head,"chandu");

    inOrderTraversal(head);
    cout<<endl;
    return 0;
}

Output :

karan sameer palak jagdish naman umang chandu

Expected:

chandu jagdish karan naman palak sameer umang

A question like this has already been asked before but that had some compilation error. My code is not throwing any error but there seems to be some logical flaw!

Dannyu NDos · Accepted Answer · 2017-01-16T07:37:02.090

In addition to rachitmanit's answer, I felt like you are writing in C, not C++.

char data[50];

In case you are writing in C++, I recommend using std::string. It can be compared conveniently with ==, <, etc.

NODE newNode = (NODE) malloc (sizeof(struct Node));

Old C's malloc only allocates memory, and doesn't construct object (i.e. doesn't call constructor). It should be: NODE newNode = new Node;

(*head)->right = NULL;
(*head)->left = NULL;
/*etc...*/

NULL is usually 0, which is an integer, not a pointer. I definitely recommend using nullptr.

void insertNode(NODE* head,char data[]){

Usually, pointer arguments might be nullptr and you should check if it is. I recommend using reference, where you don't have to: void insertNode(NODE &head, std::string data){

cout<<endl;

Should be std::cout<<std::endl.

And don't forget to deallocate the memory. Your program allocates memory and doesn't deallocate it, which will cause memory leak. struct Node should deallocate the memory when destroyed:

struct Node {
    std::string data;
    Node *right;
    Node *left;
    ~Node() {
        delete right;
        delete left;
    }
};
/* ... */
int main() {
    /* ... */
    delete head;
    return 0;
}

Thanx a lot..!! Actually i did tried using strings instead of character array.. But there was a segmentation fault and i couldn't resolve it so i decided to use character array!! — Kenil Patel, Jan 16 '17 at 15:35
Again, `malloc` doesn't call any constructor, and so doesn't call member `std::string`'s constructor. Probably that's why you got segmentation fault. — Dannyu NDos, Jan 17 '17 at 01:26

score 1 · Answer 2 · edited May 23 '17 at 12:25

1

In case of integers, your "data" is actually a value. While here "node->data" is the address of the first block of data[] array. Remember node->data[0] is a value. You are comparing addresses here not the actual "Value".

Also, you have to follow this: How to compare string in an character array?

This should help.

edited May 23 '17 at 12:25

Community

1
1

answered Jan 16 '17 at 06:24

rachitmanit

324
3
12

Binary search tree of strings implementation in c++

2 Answers2