C Data Structures: Binary Trees & Binary Search Trees (BST) Masterclass

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

static TreeNode *new_node(int val) {
    TreeNode *n = malloc(sizeof(TreeNode));
    if (!n) { perror("malloc"); exit(1); }
    n->data = val; n->left = n->right = NULL;
    return n;
}

TreeNode *bst_insert(TreeNode *root, int val) {
    if (!root) return new_node(val);
    if (val < root->data)       root->left  = bst_insert(root->left,  val);
    else if (val > root->data)  root->right = bst_insert(root->right, val);
    /* val == root->data: ignore duplicates */
    return root;
}

int bst_search(const TreeNode *root, int val) {
    if (!root) return 0;
    if (val == root->data) return 1;
    return (val < root->data)
         ? bst_search(root->left, val)
         : bst_search(root->right, val);
}

void inorder(const TreeNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int height(const TreeNode *root) {
    if (!root) return 0;
    int l = height(root->left), r = height(root->right);
    return 1 + (l > r ? l : r);
}

void free_tree(TreeNode *root) {
    if (!root) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main(void) {
    TreeNode *root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = bst_insert(root, values[i]);

    printf("In-order (sorted): "); inorder(root); printf("\n");
    printf("Tree height: %d\n", height(root));
    printf("Search 40: %s\n", bst_search(root, 40) ? "Found" : "Not Found");
    printf("Search 99: %s\n", bst_search(root, 99) ? "Found" : "Not Found");

    free_tree(root);
    return 0;
}