1

I am not from a computer science background and have been trying to learn Data Structures using C programming.

I have made some binary tree programs and realised that I have used malloc() left and right (pun intended :)) without ever using free() because I don't know how many nodes I have actually created.

My question is rather basic and almost stupid. Do I have to write a function similar to the print function to visit each node of the tree and free it individually or just free(root) will be enough since all the subsequent pointers will be lost anyway?

Improve this question
10
  • 8
    The rule is simple: for every malloc call, you should have a correlative free call (with the address you got from that malloc). Commented Nov 25, 2024 at 5:06
  • 6
    "Do I have to write a function similar to the print function to visit each node of the tree and free it individually" Yes this is the normal and expected thing to do. Commented Nov 25, 2024 at 5:13
  • 4
    Once you free memory you cannot safely access it again, so in the case of a linked list, you might have to free the nodes in reverse order, starting at the tail. Commented Nov 25, 2024 at 5:33
  • 2
    You could get around it by allocating a huge block of memory at start of the program, and creating your own my_malloc() function to dole out pieces of that huge memory block. Then when finished, you only need to free that one huge block you allocated in the beginning. It's arguably very bad practice and having a very bad motive, but it's great to know there is always another way to do something in C, and possibly a great learning experience as you work out the code for it. Commented Nov 25, 2024 at 6:07
  • 2
    @gregspears I'd argue that that approach is the only valid one for allocating large amounts of smallish (<1KB) heterogeneous objects. Trees, lists, etc. are a perfect use case; you allocate a number of items in one go and then release the block when no items in the block remain in use. Allocating and releasing individual items will then be orders of magnitude faster than otherwise. Commented Nov 25, 2024 at 7:26

1 Answer 1

Reset to default
5

When using malloc() in C to allocate memory for nodes in a binary tree, calling free(root) will not automatically free the memory of the child nodes. The tree structure consists of pointers, so while root will be freed, the left and right child pointers may still point to memory that has not been deallocated.

To properly free all the nodes, you should traverse the tree and free each node individually. This is typically done using a post-order traversal (where you visit the left and right children before freeing the current node).

example of how you might implement this:

void freeTree(struct Node* root) {
    if (root == NULL)
        return;

    freeTree(root->left);  // Free left subtree
    freeTree(root->right); // Free right subtree
    free(root);            // Free current node
}

Note:
if the binary tree is highly unbalanced (i.e., resembling a linked list), this recursive approach could lead to a stack overflow due to deep recursion. In such case we can use an iterative approach, such as using a stack to simulate the recursive calls, or by flattening the tree into a linked list structure and freeing the nodes iteratively.

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

4 Comments

This answer is acceptable when the tree is balanced, i.e. there will never be a branch several thousand nodes deep. Otherwise, this approach can result in a stack overflow.
if the binary tree is highly unbalanced (i.e., resembling a linked list), this recursive approach could lead to a stack overflow due to deep recursion. In such case we can use an iterative approach, such as using a stack to simulate the recursive calls, or by flattening the tree into a linked list structure and freeing the nodes iteratively.
@user30482 While you are correct that recursion is evil in general, something containing that much data should probably not be stored in a BST to begin with, but maybe a hash table etc.
@Lundin BST makes a lot more sense than a hash table when you want to keep the data in a particular order and to be able to iterate over the elements in that order. Unbalanced BSTs are useful as ordered data structures for thread- and interrupt-safe contexts.

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.