I have tried to implement my Binary Search Tree in C. The following are the 18 operations defined:
- create a bst
- is_empty
- insert
- delete
- clear
- find
- find_min
- find_max
- height
- size
- depth
- level order traversal
- preorder traversal
- inorder traversal
- postorder traversal
- inorder successor
- is_bst (is the tree a binary search tree)
- is_bst_balanced (is the binary search tree balanced)
This was an important phase in my coding skills to understand what recursion really is. I usually have a table of returns and a recursive call stack both drawn to track the running of recursion, and that helped immensely to grasp the background work of recursion. If you find any improvement to be said about some recursive functions in this BST implementation, I would be grateful to read them through.
This is the entire code. I have included my Queue because I needed for the level_order
function.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define max(x, y) (((x) > (y)) ? (x) : (y))
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
//---------------Queue-----------------
typedef struct QNode {
Node* data;
struct QNode* next;
} QNode;
typedef struct Queue {
int size;
QNode* head;
QNode* tail;
} Queue;
const Queue queue_init = { .size = 0, .head = NULL, .tail = NULL };
QNode* create_node(Node* elm) {
QNode* node = malloc(sizeof * node);
if (!node) return node;
node->data = elm;
node->next = NULL;
return node;
}
int is_empty_q(Queue *q) {
return q->tail == NULL;
}
QNode* tail_prev(Queue *q) {
QNode* node = q->head, *prev = NULL;
while (node->next) {
prev = node;
node = node->next;
}
return prev;
}
void enqueue(Queue *q, Node* elm) {
QNode* updated_head = create_node(elm);
if (!q->head) {
q->head = updated_head;
q->tail = q->head;
}
else {
updated_head->next = q->head;
q->head = updated_head;
}
q->size++;
}
Node* dequeue(Queue *q) {
if (!is_empty_q(q)) {
QNode* node = q->tail;
Node* elm = q->tail->data;
q->tail = tail_prev(q);
if (q->tail) {
q->tail->next = NULL;
}
else {
q->head = NULL;
}
free(node);
q->size--;
return elm;
}
return NULL;
}
Node* front(Queue *q) {
Node* front;
if (q->tail)
front = q->tail->data;
else
front = NULL;
return front;
}
void clear_q(Queue *q) {
while (q->tail)
dequeue(q);
printf("Queue Cleared");
}
//---------------BST------------------
typedef struct BST {
Node* root;
} BST;
const BST bst_init = { .root = NULL };
Node* create_node_bst(int elm) {
Node* node = malloc(sizeof * node);
if (!node) return node;
node->data = elm;
node->left = node->right = NULL;
return node;
}
BST* create_bst() {
BST* bst = malloc(sizeof * bst);
if (!bst) return bst;
bst->root = NULL;
return bst;
}
int is_empty(Node* root) {
return root == NULL;
}
Node* insert(Node* root, int elm) { // -V
if (!root) {
root = create_node_bst(elm);
}
else if (elm <= root->data) {
root->left = insert(root->left, elm);
}
else {
root->right = insert(root->right, elm);
}
return root;
}
Node* find(Node* root, int elm) { // -V
if (!is_empty(root)) {
if (!root) {
root = NULL;
}
else if (root->data == elm) {
root = root;
}
else if (elm <= root->data) {
root = find(root->left, elm);
}
else {
root = find(root->right, elm);
}
return root;
}
else
return root;
}
Node* find_max(Node* root) { //-V
if (!is_empty(root)) {
if (root->right == NULL)
return root;
else {
return find_max(root->right);
}
}
else
return root;
}
Node* find_min(Node* root) { //-V
if (!is_empty(root)) {
if (!root->left)
return root;
else {
return find_min(root->left);
}
}
else
return root;
}
int height(Node* root) {
if (root == NULL) {
return -1; // 0 if heighe is number of edges, or -1 if height=number of edges
}
int left_height = height(root->left);
int right_height = height(root->right);
return max(left_height, right_height) + 1;
}
int depth(Node* root, int elm) {
if (root->data == elm) {
return 0;
}
else if (elm < root->data) {
return depth(root->left, elm) + 1;
}
else {
return depth(root->right, elm) + 1;
}
}
Node* delete(Node* root, int elm) {
if (root == NULL)
return root;
else if (elm > root->data)
root->right = delete(root->right, elm);
else if (elm < root->data)
root->left = delete(root->left, elm);
else { // elm found
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
}
else if (root->left == NULL) {
Node* temp = root;
root = root->right;
free(temp);
}
else if (root->right == NULL) {
Node* temp = root;
root = root->left;
free(temp);
}
else { //this case is done until it is reduced to one of the previous three cases
Node* temp = find_min(root->right);
root->data = temp->data;
root->right = delete(root->right, elm);
}
}
return root;
}
int is_bst(Node* root, int min, int max) { // solution 1
if (root == NULL) {
return 1;
}
else if (root->data < max && root->data > min && is_bst(root->left, min, root->data) && is_bst(root->right, root->data, max))
return 1;
else
return 0;
} // solution 2, traverse inorder and check if the list is sorted
int is_bst_balanced(Node* root) {
int is_balanced = 1;
int left_height = height(root->left);
int right_height = height(root->right);
if (abs(right_height - left_height) > 1)
is_balanced = 0;
return is_balanced;
}
int size(Node* root) {
if (!root)
return 0;
int left_size = size(root->left);
int right_size = size(root->right);
return left_size + right_size + 1; // + 1 is for the ancesstor
}
void level_order(Node* root) { // visit all children before grand children
if (!is_empty(root)) {
Queue *q = malloc(sizeof *q);
if (q) {
*q = queue_init;
enqueue(q, root);
while (!is_empty_q(q)) {
Node* cur = front(q);
printf("%d ", cur->data);
if (cur->left != NULL)
enqueue(q, cur->left);
if (cur->right != NULL)
enqueue(q, cur->right);
dequeue(q);
}
}
}
}
void pre_order(Node* root) { //D<root>L<left>R<right> -- preorder (of root)
if (root) {
printf("%d ", root->data);
pre_order(root->left);
pre_order(root->right);
}
}
void in_order(Node* root) { //L<left>D<root>R<right> -- inorder -- gives sorted list
if (root) {
in_order(root->left);
printf("%d ", root->data);
in_order(root->right);
}
}
Node* in_order_suc(Node* root, int data) {
Node* cur = find(root, data);
if (!cur)
return cur;
if (cur->right != NULL) { //case 1: node has sub tree
return find_min(cur->right);
}
else { //case 2: no right sub tree
Node* suc = NULL, *prev = root;
while (prev != cur) {
if (cur->data < prev->data) {
suc = prev;
prev = prev->left;
}
else {
prev = prev->right;
}
}
return suc;
}
}
void post_order(Node* root) { //L<left>R<right>R<root> -- postorder
if (root) {
post_order(root->left);
post_order(root->right);
printf("%d ", root->data);
}
}
Node* clear(Node* root) {
while (root) {
root = delete(root, root->data);
}
return root;
}
int main() {
#define MAX 8
int n = MAX;
BST bst1 = bst_init;
Node* bst1_root = bst1.root;
int arr[MAX] = {15, 10, 20, 9, 13, 19, 22, 18};
if (!arr) return 0;
for (int i = 0; i < n; i++)
bst1_root = insert(bst1_root, arr[i]);
printf("height: %d \n", height(bst1_root));
printf("size: %d \n", size(bst1_root));
printf("depth of 13: %d \n", depth(bst1_root, 18));
printf("is_bst: %d \n", is_bst(bst1_root, -1000, 1000)); //assuming -1000 < data(bst) < 1000
printf("is_bst_balanced: %d \n", is_bst_balanced(bst1_root));
printf("min: %d \n", find_min(bst1_root)->data);
printf("max: %d \n", find_max(bst1_root)->data);
printf("element: %d found \n", find(bst1_root, 19)->data);
printf("level order ");
level_order(bst1_root);
printf("\n");
printf("preorder order ");
pre_order(bst1_root);
printf("\n");
printf("inorder order ");
in_order(bst1_root);
printf("\n");
printf("postorder order ");
post_order(bst1_root);
printf("\n");
printf("inorder successor of 9 is %d \n", in_order_suc(bst1_root, 9)->data);
bst1_root = delete(bst1_root, 18);
printf("in order ");
in_order(bst1_root);
printf("\n");
bst1_root = insert(bst1_root, 18);
printf("in order ");
in_order(bst1_root);
bst1_root = clear(bst1_root);
printf("\n");
if (!bst1_root)
printf("BST Cleared!");
return 0;
}
typedef
ofBST
. Why isn't it used in what interface there is? \$\endgroup\$BST doesn't allow duplicates, no?
I don't know any authoritative definition of BST: up to you. You don't need/want duplicates in sets. When there is ("payload") data associated with keys, duplicates may be essential. \$\endgroup\$is enough to …
write tests, have them executed automatically. This is not chat. \$\endgroup\$int arr[MAX] = {15, 10, 20, 9, 13, 19, 22, 18}; if (!arr) return 0;
===> doesn't make sense. The address ofarr
will always evaluate astrue
. \$\endgroup\$main()
. You did notfree()
the memory allocated bylevel_order()
. \$\endgroup\$