Freeing (or deallocating) a Binary Tree in C

main.c
#include <stdlib.h>
#include <stdio.h>

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

TreeNode* new_node(int val) {
    TreeNode* n = malloc(sizeof(TreeNode));
    n->val = val;
    n->left = NULL;
    n->right = NULL;
    return n;
}

void print_depth_first(TreeNode* root) {
    TreeNode* process_stack[100];
    size_t process_stack_num = 0;
    process_stack[0] = root;
    process_stack_num++;

    while (process_stack_num > 0) {
        TreeNode* current = process_stack[process_stack_num - 1];
        process_stack_num--;

        if (current->val == 4) {
            printf("%d(yay we found the node 4) ", current->val);
            break;
        } else {
            printf("%d ", current->val);
        }

        if (current->right != NULL) {
            process_stack[process_stack_num] = current->right;
            process_stack_num++;
        }
        if (current->left != NULL) {
            process_stack[process_stack_num] = current->left;
            process_stack_num++;
        }
    }
}

void print_breadth_first(TreeNode* root) {
    TreeNode* process_queue[100];
    size_t process_queue_num = 0;
    process_queue[0] = root;
    process_queue_num++;

    while (process_queue_num > 0) {
        TreeNode* current = process_queue[0];
        int i;
        for (i = 0; i < process_queue_num - 1; i++) {
            process_queue[i] = process_queue[i + 1];
        } 
        process_queue_num--;

        if (current->val == 4) {
            printf("%d (yay, we found 4) ", current->val);
        } else {
            printf("%d ", current->val);
        }

        if (current->left != NULL) {
            process_queue[process_queue_num] = current->left;
            process_queue_num++;
        }
        if (current->right != NULL) {
            process_queue[process_queue_num] = current->right;
            process_queue_num++;
        }
    }
}

int found = 0;
void print_depth_first_recursive(TreeNode* node) {
    if (found == 1) {
        return;
    }
    if (node->val == 4) {
        printf("%d (yay we found 4) ", node->val);
        found = 1;
        return;
    } else {
        printf("%d ", node->val);
    }

    if (node->left != NULL) {
        print_depth_first_recursive(node->left);
    }
    if (node->right != NULL) {
        print_depth_first_recursive(node->right);
    }
}

void free_binary_tree_queue(TreeNode* root) {
    TreeNode* process_queue[100];
    size_t process_queue_num = 0;
    process_queue[0] = root;
    process_queue_num++;

    int i = 0;
    while (i < process_queue_num) {
        TreeNode* current = process_queue[i];
        i++;

        if (current->left != NULL) {
            process_queue[process_queue_num] = current->left;
            process_queue_num++;
        }
        if (current->right != NULL) {
            process_queue[process_queue_num] = current->right;
            process_queue_num++;
        }
        free(current);
    }

    // for (i = process_queue_num - 1; i >= 0; i--) {
    //     free(process_queue[i]);
    // }
}

void free_binary_tree_stack(TreeNode* root) {
    TreeNode* process_stack[100];
    size_t process_stack_num = 0;
    process_stack[0] = root;
    process_stack_num++;

    while (process_stack_num > 0) {
        TreeNode* current = process_stack[process_stack_num - 1];
        process_stack_num--;

        if (current->right != NULL) {
            process_stack[process_stack_num] = current->right;
            process_stack_num++;
        }
        if (current->left != NULL) {
            process_stack[process_stack_num] = current->left;
            process_stack_num++;
        }
        free(current);
    }
}

//     0
//   /   \
//  1     2
// / \   / \
//3  4  5  6
int main(int argc, char* argv[]) {
    TreeNode* root = new_node(0);
    root->left = new_node(1);
    root->right = new_node(2);
    root->left->left = new_node(3);
    root->left->right = new_node(4);
    root->right->left = new_node(5);
    root->right->right = new_node(6);

    print_depth_first_recursive(root);
    free_binary_tree_queue(root);
    return 0;
}
CodeVault Supporter

If you find our content useful and has helped you in the past, you can help the CodeVault community grow by becoming a CodeVault supporter