logo

Freeing (or deallocating) a Binary Tree in 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; }