i have implemented a tree in C:

struct node
{
    char *key;
    struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(char *item)
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
    if (root != NULL)
    {
        inorder(root->left);
        printf("%s\n", root->key);
        inorder(root->right);
    }
}

/* A utility function to
   insert a new node with given key in
 * BST */
struct node *insert(struct node *node, char *key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL)
        return newNode(key);

    /* Otherwise, recur down the tree */
    if (strcmp(key, node->key) < 0)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

/* Given a non-empty binary search
   tree, return the node
   with minimum key value found in
   that tree. Note that the
   entire tree does not need to be searched. */
struct node *minValueNode(struct node *node)
{
    struct node *current = node;

    /* loop down to find the leftmost leaf */
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

/* Given a binary search tree
   and a key, this function
   deletes the key and
   returns the new root */
struct node *deleteNode(struct node *root, char *key)
{
    // base case
    if (root == NULL)
        return root;

    // If the key to be deleted
    // is smaller than the root's
    // key, then it lies in left subtree
    if (strcmp(key, root->key) < 0)
        root->left = deleteNode(root->left, key);

    // If the key to be deleted
    // is greater than the root's
    // key, then it lies in right subtree
    else if (strcmp(key, root->key) > 0)
        root->right = deleteNode(root->right, key);

    // if key is same as root's key,
    // then This is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        // node with two children:
        // Get the inorder successor
        // (smallest in the right subtree)
        struct node *temp = minValueNode(root->right);

        // Copy the inorder
        // successor's content to this node
        root->key = temp->key;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

I have defined a function that takes the Tree as input and deletes a node from it if a condition is met:

void applyFilter(struct node *Tree)
{
    if (Tree != NULL)
    {
        applyFilter(Tree->left);
        applyFilter(Tree->right);
        for (short i = 0; i < MAX_CONSTRAINTS; i  )
        {
             if (strchr(Tree->key, constraints[i].letter) != NULL)
                    {
                        // delete the word from the tree
                        Tree = deleteNode(Tree, Tree->key);
                        break;
                    }
                }
            }
        }

But i got segmentation fault. The main goal is to make it work, with as little memory as possible (running). I think I understand the problem, and it is caused by recursion, because if I delete a node it will give me an empty tree. If you can give me an example, even a different one i will be really gratefull, because i worked on it a lot, but i am totally stucked.

Thank you!

It happens in minValueNode() after the call of the deleteNode(), because result that the Tree is empty

CodePudding user response：

It happens in minValueNode() after the call of the deleteNode(), because result that the Tree is empty

Basically you already understand what the problem is. You will need to check whether the tree is empty and default the value to something inside minValueNode before you start looping. Because the loop assumes that you have something and if you happen to have nothing, then it's a faulty assumption and causes segfault.