binarySearchTree.c

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

typedef struct _node {
    int data;
    struct _node *left, *right;
} node;

node *root = NULL;

node *createNode(int data) {
    node *newNode = malloc(sizeof(node));

    newNode -> data = data;
    newNode -> left = newNode -> right = NULL;

    printf("Node %d created\n", data);

    return newNode;
}

node *findNode(node *tree, int data) {
    if (tree == NULL) {
        return NULL;
    }

    printf("%d ", tree -> data);

    if (data == tree -> data) {
        return tree;
    }

    if (data < tree -> data) {
        return findNode(tree -> left, data);
    }

    return findNode(tree -> right, data);
}

node *insertNode(node *tree, int data) {
    if (root == NULL) {
        root = createNode(data);
        return NULL;
    }

    if (tree == NULL) {
        return createNode(data);
    }

    if (data < tree -> data) {
        tree -> left = insertNode(tree -> left, data);
    }
    else {
        tree -> right = insertNode(tree -> right, data);
    }
}

void inorderTraverse(node *tree) {
    if (tree != NULL) {
        inorderTraverse(tree -> left);
        printf("%d ", tree -> data);
        inorderTraverse(tree -> right);
    }
}

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

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

int main(void) {
    printf("Creating tree...\n");
    insertNode(root, 39);
    insertNode(root, 56);
    insertNode(root, 12);
    insertNode(root, 34);
    insertNode(root, 78);
    insertNode(root, 32);
    insertNode(root, 10);
    insertNode(root, 89);
    insertNode(root, 54);
    insertNode(root, 67);
    insertNode(root, 81);

    printf("\nInorder Traverse: ");
    inorderTraverse(root);

    printf("\nPreorder Traverse: ");
    preorderTraverse(root);

    printf("\nPostorder Traverse: ");
    postorderTraverse(root);

    printf("\nFinding 8: ");
    printf("%s", findNode(root, 8) ? "Found!" : "Not found!");

    printf("\nFinding 10: ");
    printf("%s\n", findNode(root, 10) ? "Found!" : "Not found!");

    return 0;
}