Delete left subtree node (binary search tree) in C

Question

I am working on a C binary search tree library and I'm trying to write a function that will delete the left node of the tree subtree. Here's the struct of my tree:

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

typedef struct Node TNode;
typedef struct Node *binary_tree;

The tree is created like this:

binary_tree NewBinaryTree(int value_root) {
    binary_tree newRoot = malloc(sizeof(TNode));
    if (newRoot) {
        newRoot->value = value_root;
        newRoot->left = NULL;
        newRoot->right = NULL;
    }
    return newRoot;
}

Adding element to it:

void Insert(binary_tree *tree, int val) {
    if (*tree == NULL) {
        *tree = (binary_tree)malloc(sizeof(TNode));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
    } else {
        if (val < (*tree)->value) {
            Insert(&(*tree)->left, val);
        } else {
            Insert(&(*tree)->right, val);
        }
    }
}

The delleftsubtreenode I did:

void delleftsubtree(binary_tree *tree){

    if( (*tree)->value!=NULL )

    {
            free(&(*tree)->left);
            delleftsubtree( &(*tree)->left);
    }
    else
    {
        printf("end");
    }
}

This method compile,however when I try to call it the program just crash.I dont understand why or how else to do that function.

thank you!

There are a number of problems with your code, which begin with you passing around binary_tree * values instead of binary_tree. You are also testing an integer with NULL, and you are deleting a tree node before recursing into it. — paddy
– paddy, Commented Dec 14, 2016 at 2:08
*Never ever typedef pointers! You already see the negative effects of this malpractice. — too honest for this site
– too honest for this site, Commented Dec 14, 2016 at 2:35

Daniel · Accepted Answer · 2016-12-14 03:22:21Z

2

As Olaf said in his comment, you have several problems; calling "free()" with a pointer then attempting to dereference it, and use of double indirection.

binary_tree* tree; /* why use a pointer to a pointer? */

Unless you intend to change the value of the pointer, this is extra work you don't want to be doing. All those "(*tree)->member" expressions are not needed if you follow the usual conventions, and I'm not convinced that you understand what "&(*tree)->left" is doing.

I'm not saying that you should never use a pointer to a pointer, I've done it myself, however you should only do it when there is a reason to be changing the value of the referenced pointer, or with a volatile pointer that might be changed by some external actor; this is unlikely and fairly rare outside of garbage collected and compacted pools (strings in some BASIC interpreters, for example) and the like.

Keep in mind that the "left" subtree of a node in the tree is a binary tree itself; it has both left and right nodes. You need to write a function that deletes a subtree at and below a given node. Once that's understood, removal of the left subtree below a node is as simple as:

void delSubtree(NodeT* subRoot)
{
   if (subRoot != NULL)
   {
      delSubtree(subRoot->left);
      delSubtree(subRoot->right);
      free(subRoot);
   }
}

void delLeftSubtree(NodeT* root)
{
   if (root != NULL)
   {
      delSubtree(root->left);
      root->left = NULL;
   }
}

If this is homework, you should be solving these problems yourself, and I'm doing you no favors in giving you code samples. Understanding how to use pointers and linked data structures (lists, trees, and other graphs) is essential to becoming an accomplished C programmer.

answered Dec 14, 2016 at 3:22

Daniel

818 bronze badges

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

3 Comments

Christopher M. Over a year ago

This isnt for a homework.Thank you for your help.Is it possible to delete for example the left subtree node without deleting the entire left subtree?What is going to happen?I mean if I just delete the left subtree node I would need to "link" back all the other children nodes

Daniel Over a year ago

@ChristopherM.: Removal of an interior node is possible, but more complicated because you must keep the traversal order of the remaining nodes the same.

Daniel Over a year ago

http://www.algolist.net/Data_structures/Binary_search_tree/Removal has some good illustrations of what needs to be done for various cases (node to be deleted has no children (leaf node), one child, two children).

Collectives™ on Stack Overflow

Delete left subtree node (binary search tree) in C

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related