CODEWITHSUNDEEP
c++stringbinary-search-tree
Kenil Patel
Kenil Patel

Reputation: 105

Binary search tree of strings implementation in c++

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!

Upvotes: 0

Views: 9740

Answers (2)

Dannyu NDos
Dannyu NDos

Reputation: 2498

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

Upvotes: 2

rachitmanit
rachitmanit

Reputation: 334

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.

Upvotes: 1

Related Questions