CODEWITHSUNDEEP
cpointersbinary-treefree
Ambareesh S J
Ambareesh S J

Reputation: 97

How to delete elements in a binary tree in C?

I'm trying to understand the deletion of nodes in a binary tree. This is the code snippet that I found from the tutorial which explains the same.

The node looks like this:

struct node
{
  int key_value;
  struct node *left;
  struct node *right;
};

Source : http://www.cprogramming.com/tutorial/c/lesson18.html

    void destroy_tree(struct node *leaf)
    {
      if( leaf != 0 )
      {
          destroy_tree(leaf->left);
          destroy_tree(leaf->right);
          free( leaf );
      }
    }

My doubt is regarding the free(leaf) part. I mean, the author claims that this will recursively delete all the nodes starting from the bottom left most one. But isn't free(leaf) just freeing the memory of the leaf pointer? Aren't all the nodes still connected? How does the clearing take place?

Upvotes: 5

Views: 2852

Answers (7)

user905
user905

Reputation: 260

Lets try to understand it from this code:

void delete(struct node* node)
{
if(node==NULL)
return;
delete(node->left);
delete(node->right);
free(node)
}

In this code control will go to the left most leaf first and it will start deleting from there (as before deleting a parent we will have to delete its children) lets take a tree for example:

     1
    / \
   2    3
  / \
 4   5

so first the memory for node 4 will be freed and then for node 5, as free does not return any value(memory reference gets deleted) so the parent node will also be pointing to NULL, so after 5 2 will get deleted. I hope this helps.

Upvotes: 1

2bigpigs
2bigpigs

Reputation: 462

The free(leaf) call frees the memory which was allocated for the variable which is being pointed to by the pointer leaf. Here, It frees all the 12 bytes that a variable of type struct node takes up - i.e. the 4 bytes for the int value, the 4 bytes for the node *left pointer and the 4 bytes for the node *right pointer.

By calling destroy_tree(left), you're deleting the subtree pointed to by left. You can think of it as setting fire to the top of the tree and watching it burn down from the leaves, First the left branch, then the right branch.

Upvotes: 1

Alikbar
Alikbar

Reputation: 696

It is deleting the leaf and it's branches in a recursive way. I draw a sample for you. The numbers in the circle shows the order of leafs being freed. The lines show the order of code execution

enter image description here

Upvotes: 2

Aleksandar Makragić
Aleksandar Makragić

Reputation: 1997

I'm showing you graphically how would tree change:

START: 

                  10
               /      \
              6        14
             / \       /  \
            free 8    11    18

                  10
               /      \
              6           14
             /   \       /  \
            free free  11    18


                  10
               /       \
              free        14
             /   \       /  \
            free  free  11  18


                   10
                /       \
              free         14
             /   \       /    \
            free  free  free  18

                   10
                 /       \
              free         14
             /   \       /     \
            free  free  free  free

                     10
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

                    free
                 /       \
              free         free
             /   \       /     \
            free  free  free  free

Of course in the end, nodes are not connected, they no longer exist. I just showed in picture how would they change during the course of this algorithm. If you have any further questions, feel free to ask.

I strongly suggest you that, whenever you can't understand how tree recursion work, on piece of paper write a picture and then go trough algorithm like I wrote above.

Upvotes: 3

datenwolf
datenwolf

Reputation: 162164

But isn't free(leaf) just returning the memory of the leaf pointer?

Yes. But that's not the whole story. Look just above the call to free, what do you see being called?

Aren't all the nodes still connected?

Doesn't matter because…

How does the clearing take place?

the recursive calls of destroy_tree descending down left and right, which will in turn do recursive destruction, and at the end it frees, returns to the caller, which frees and so on. At the end the whole tree has been freed.

Upvotes: 1

Sean
Sean

Reputation: 62472

In the link you've posted the author has a tree that looks like this:

                         10
                       /    \
                      6      14
                     / \    /  \
                    5   8  11  18

The recursive delete function works by going all the way down the left side, then the right side then deleting the node. So in the above the following will happen (starting with the node containing 10)

Node 10 -> leaf!=null -> destroy_leaf(leaf->left)
  Node 6 -> leaf!=null -> destroy_leaf(leaf->left)
    Node 5 -> leaf!=null -> destroy_leaf(leaf->left)
      null -> do nothing and return back to Node 5
    Node 5 - destroy_leaf(leaf->right)
      null -> do nothing and return back to Node 5
    free(Node 5) and return back to Node 6
  Node 6 -> destroy->leaf(leaf->right)
    Node 8 -> leaf!=null -> destroy_leaf(leaf->left)
      null -> do nothing and return back to Node 8
    Node 8 -> destroy_leaf(leaf->right)
      null -> do nothing and return back to Node 8
    free(node 8) and return back to Node 6
  free(node 6) and return back to Node 10
Node 10 -> destroy_left(leaf->right)

The above shows how the function will recurse down the left side from node 10. As the nodes are freed their parent will point to memory that has been released, but this is fine as you will ultimately discard the parent node when the recursion unwinds and frees the parent.

Upvotes: 2

mrmemio29
mrmemio29

Reputation: 398

You are correct. It is reclaiming the memory from C's "Allocated Memory", which is most likely the heap. Since you are deleting the WHOLE tree it doesn't matter than you aren't properly reconstructing the nodes as it recurses up the tree because they're about to be destroyed too.

This code is not deleting or rather "removing" an element from the tree, it is destroying the entire tree given a leaf node.

From the website

The destroy_tree shown below which will actually free all of the nodes of in the tree stored under the node leaf: tree.

Upvotes: 1

Related Questions