Answers for "binary search tree program"

binary tree search

/* This is just the seaching function you need to write the required code.
	Thank you. */

void searchNode(Node *root, int data)
{
    if(root == NULL)
    {
        cout << "Tree is empty\n";
        return;
    }

    queue<Node*> q;
    q.push(root);

    while(!q.empty())
    {
        Node *temp = q.front();
        q.pop();

        if(temp->data == data)
        {
            cout << "Node found\n";
            return;
        }

        if(temp->left != NULL)
            q.push(temp->left);
        if(temp->right != NULL)
            q.push(temp->right);
    }

    cout << "Node not found\n";
}

binary search tree program in c

// credit @callmemoeen

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

#define NULL 0

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

typedef struct treeNode TN;

TN *root;

TN *Delete_aux(TN *t, int item);
void print_postorder(TN *t);
void print_inorder(TN *t);
void print_preorder(TN *t);
void Delete(int item);

void init_tree()
{
    root = NULL;
}

TN *createNode(int item)
{
    TN *temp = (TN *)malloc(sizeof(TN));
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void print_tree_aux(TN *t, int depth)
{
    if (t == NULL)
        return;

    print_tree_aux(t->right, depth + 1);
    for (int i = 0; i < depth; i++)
        printf("\t");
    printf("%d---------------------------------\n", t->data);
    print_tree_aux(t->left, depth + 1);
}

void print_tree()
{
    printf("Printing tree ************************************\n");
    print_tree_aux(root, 0);
    printf("Complete ************************************\n");
}

TN *insert_aux(TN *t, int item)
{

    if (t == NULL)
    {
        return createNode(item);
    }

    if (item < t->data)
    {
        t->left = insert_aux(t->left, item);
        return t;
    }
    else
    {
        t->right = insert_aux(t->right, item);
        return t;
    }
}

void insert(int item)
{
    root = insert_aux(root, item);
}

TN *search_aux(TN *t, int key)
{
    if (t == NULL)
        return NULL;
    if (t->data == key)
        return t;
    else if (t->data > key)
        return search_aux(t->left, key);
    else
        return search_aux(t->right, key);
}

TN *search(int key)
{
    return search_aux(root, key);
}

TN *Leftmost(TN *t)
{
    TN *temp = t;
    while (temp->left != NULL)
    {
        temp = temp->left;
    }
    return temp;
}

TN *Delete_aux(TN *t, int item)
{
    TN *temp;
    // check if the tree is empty
    if (t == NULL)
        return NULL;
    // find the node with the arguement value recursively
    if (t->data > item)
    {
        t->left = Delete_aux(t->left, item);
        return t;
    }

    else if (t->data < item)
    {
        t->right = Delete_aux(t->right, item);
        return t;
    }
    else
    {
        // case 1: node with no child deletion
        if (t->left == NULL && t->right == NULL)
        {
            free(t);
            return NULL;
        }

        // case 2: 1 child only deletion. to be deleted node has a child on right branch
        else if (t->left == NULL)
        {
            temp = t->right;
            free(t);
            return temp;
        }
        // case 2: 1 child only deletion. to be deleted node has a child on left branch
        else if (t->right == NULL)
        {
            temp = t->left;
            free(t);
            return temp;
        }
        else
        {
            // get the smallest node in the right subtree temp = Leftmost(t->right)
            t->data = temp->data;
            t->right = Delete_aux(t->right, temp->data);
            return t;
        }
    }
}

void Delete(int item)
{
    TN *temp;
    // search() returns the node that contains the flag value
    temp = search(item);
    Delete_aux(root, item); 
}
void print_preorder(TN *t)
{
    if (t == NULL)
        return;

    printf("%d ", t->data);   // root
    print_preorder(t->left);  // left
    print_preorder(t->right); // right
}

void print_inorder(TN *t)
{
    if (t == NULL)
        return;

    print_inorder(t->left);  // left
    printf("%d ", t->data);  // root
    print_inorder(t->right); // right
}

void print_postorder(TN *t)
{
    if (t == NULL)
        return;

    print_postorder(t->left);  // left
    print_postorder(t->right); // right
    printf("%d ", t->data);    // root
}

int main()
{
    init_tree();

    insert(50);
    insert(30);
    insert(60);
    insert(20);
    insert(15);
    insert(5);
    insert(45);
    insert(75);
    insert(40);
    insert(90);
    insert(65);
    insert(70);
    print_tree(root, 0);

    if (search(65) == NULL)
        printf("%d not found\n", 65);
    else
        printf("%d found\n", 65);

    if (search(95) == NULL)
        printf("%d not found\n", 95);
    else
        printf("%d found\n", 95);

    print_inorder(root);
    printf("\n");

    print_preorder(root);
    printf("\n");

    print_postorder(root);
    printf("\n");

    Delete(5);
    print_tree();

    Delete(70);
    print_tree();

    return 0;
}