binary_tree.c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void add(struct Node** root, int data) {
    // Create a new node
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;

    // Check if our tree is empty
    if (*root == NULL) {
        *root = newNode;
        return;
    }

    // Traverse the tree 
    struct Node* curNode = *root;
    struct Node* parent = NULL;
    while (curNode != NULL) {
        parent = curNode;
        if (data < curNode->data) {
            curNode = curNode->left;
        } else {
            curNode = curNode->right;
        }
    }

    // We found a leaf node, lets the mount our new node
    if (data < parent->data) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
}

int search(struct Node* root, int key) {
    // If null, return false
    if (root == NULL) {
        return 0;
    }

    // Check the root
    if (root->data == key) {
        return 1;
    }

    // Search down appropriate subtree
    if (key < root->data) {
        return search(root->left, key);
    } else {
        return search(root->right, key);
    }
}

void inorderTraversal(struct Node *root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

int main() {

    struct Node* head = NULL;

    add(&head, 4);
    add(&head, 2);
    add(&head, 1);
    add(&head, 6);
    add(&head, 7);
    add(&head, 8);

    inorderTraversal(head);
    printf("\n");

    printf("Search for 4\n");
    int result = search(head, 4);
    if (result == 1) {
        printf("Found it!\n");
    } else {
        printf("Did not find it\n");
    }

    return 0;
}