0

I am trying to create a binary search tree that deletes the 2 leftmost nodes in a bst. For some reason, my code deletes the first value twice instead of moving onto the next.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct treeNode {
    char *word;                         // the string word that is stored
    int origin;                         // position of the word in the original text input’s line 1
    struct treeNode *left;              // pointer for the left children of the node
    struct treeNode *right;             // pointer for the right children of the node
    struct treeNode *parent;            // pointer for the parent of the node
};
typedef struct treeNode NODE;

NODE *
addNode(NODE * r, char *x)
{
    // r = root pointer of the tree
    // x = value to add into this tree
    // return the root of the updated tree
    NODE *p = malloc(sizeof(NODE));

    p->word = malloc(strlen(x) + 1);
    strcpy(p->word, x);                 // strcpy input: (destination, data to be copied)
    // printf("%s", x);
    p->parent = NULL;
    p->left = NULL;
    p->right = NULL;

// if tree is empty, tree consists of p only
    if (r == NULL)
        return p;

    if (strcmp(x, r->word) > 0) {

        r->right = addNode((r->right), x);
        return r;
    }
    else {
        // add new node the left subtree
        r->left = addNode((r->left), x);
        return r;
    }

    return r;

}

NODE *
getLeftMostNode(NODE * root)
{
    // return the pointer to the right most node
    if (root == NULL)
        return NULL;
    NODE *p = root;

    while (p->left != NULL)
        p = p->left;
    return p;
}

NODE *
addTree2Tree(NODE * X, NODE * Y)
{
    if (X == NULL)
        return Y;
    if (Y == NULL)
        return X;

    X = addNode(X, Y->word);
    X = addTree2Tree(X, Y->left);
    X = addTree2Tree(X, Y->right);
    return X;
}

NODE *
removeNode(NODE * r)
{
// remove any node that store value x from tree
// r: root pointer of this tree
// return root pointer of the updated tree after removal

    NODE *p = getLeftMostNode(r);

    NODE *C = p->parent;
    NODE *A = p->left;
    NODE *B = p->right;

    if (C == NULL) {
        // p is root of the tree
        free(p);
        return addTree2Tree(A, B);      // add tree A and tree B and return the new combination tree
    }
    if (A != NULL) {
        // make A a child of C assuming position of P
        if (p == C->left)
            C->left = A;
        else
            C->right = A;
        A->parent = C;
        free(p);
        return addTree2Tree(r, B);
    }
    if (B != NULL) {
        if (p == C->left)
            C->left = B;
        else
            C->right = B;
        B->parent = C;
        free(p);
        return r;
    }
    if (p == C->left)
        C->left = NULL;
    else
        C->right = NULL;
    free(p);                            // free allocation for p
    return r;

}

void
printArray(NODE * r)
{

// print all the values on the tree rooted at node "r" // print in alphabetical order

// if the tree is empty, return // print all the values on the tree rooted at node "r" // print in the in-order order: print left first, followed by root, followed by right values

    if (r == NULL) {
        return;
    }

    else {

        printArray(r->left);            // print all values in left subtree
        printf("%s ", r->word);
        printArray(r->right);           // print all values in right subtree

    }
}

int
main()
{
    // input must be implemented by linked list, not array
    NODE *root = NULL;
    int ch;
    char in[1000];                      // input array
    int len = 0;
    char del[100];                      // word to be deleted
    char word[1000];

    while ((ch = getchar()) != '\n')
        in[len++] = ch;
    in[len] = '\0';
    // printf("%s\n", in);

    int i = 0,
        j = 0;

    while (i <= len) {
        // space to store a word
        if ((in[i] == ' ') || (in[i] == '\0') || (in[i] == '\t')) {
            word[j] = '\0';             // end of word
            j = 0;
            root = addNode(root, word);
            // printf("%s\n", word);
        }
        else
            word[j++] = in[I];
        i++;

    }
    int k = 0;

    removeNode(root);
    removeNode(root);

    printArray(root);
    printf("\n");

    return 0;
}

enter image description here

this is the error that I got

3
  • Why does addNode allocate multiple nodes recursively then leak them? Commented Dec 21, 2021 at 21:02
  • Without even looking at removeNode, we can tell that removeNode(root); is obviously wrong. What if there's only one node left in the tree? root would need to be modified. Commented Dec 21, 2021 at 22:10
  • 1
    Tip: p->word = malloc(strlen(x) + 1); strcpy(p->word, x); can be simplified to p->word = strdup(x); Commented Dec 21, 2021 at 22:14

1 Answer 1

2

The function removeNode is looking for parent, but parent is never assigned in addNode. You want to assign r->right->parent = r; and r->left->parent = r;.

BST doesn't keep duplicate keys. If strcmp(x, r->word) == 0, then don't add a new node.

addNode should also be corrected so that if r is NULL, the function returns the new node immediately.

NODE* addNode(NODE* r, char* x)
{
    if(!x) 
        return NULL;

    if (!r)
    {
        NODE* p = malloc(sizeof(NODE)); if (!p) return NULL;
        p->word = strdup(x);
        p->parent = NULL;
        p->left = NULL;
        p->right = NULL;
        return p;
    }

    if (strcmp(x, r->word) > 0) 
    {
        r->right = addNode((r->right), x);
        r->right->parent = r;
        return r;
    }
    else if (strcmp(x, r->word) < 0)
    {
        r->left = addNode((r->left), x);
        r->left->parent = r;
        return r;
    }

    return r;
}

Modify the insert functions such that root is assigned only once:

while (i <= len) 
{
    if ((in[i] == ' ') || (in[i] == '\0') || (in[i] == '\t')) 
    {
        word[j] = '\0';             
        j = 0;
        if(!root)
            root = addNode(root, word);
        else
            addNode(root, word);
    }
    else
        word[j++] = in[i];
    i++;
}

Double check the pointers to make sure NULL pointers are avoided. For example:

NODE* removeNode(NODE* r)
{
    if(!r)
        return NULL;
    NODE* p = getLeftMostNode(r);
    if(!p)
        return NULL;
    ...
}

I have not checked the rest of the code but the example will work with these changes made.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.