Q1. Binary Search Tree (BST).

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

#define ENOMEM  12

struct BSTNode {
        int data;
        struct BSTNode *left_child;
        struct BSTNode *right_child;
};

bool Search(struct BSTNode *root, int data)
{
        if (root == NULL)
                return false;
        else if(root->data == data)
                return true;
        else if (data <= root->data)
                return Search(root->left_child, data);
        else
                return Search(root->right_child, data);
}

struct BSTNode *GetNewBSTNode(int data)
{
        struct BSTNode *newNode = (struct BSTNode *)malloc(sizeof(struct BSTNode *));
        if (!newNode) {
                printf("Error in allocating memory for new node\n");
                -ENOMEM;
        }

        newNode->data = data;
        /* For each new node the left & right child will be NULL */
        newNode->left_child = newNode->right_child = NULL;

        return newNode;
}

void Insert(struct BSTNode **root, int data)
{
        /* Empty Tree */
        if (*root == NULL)
                *root = GetNewBSTNode(data);
        else if (data <= (*root)->data) //left sub-tree
                Insert(&(*root)->left_child, data);
        else
                Insert(&(*root)->right_child, data);
}

void PrintNode(struct BSTNode *root)
{
        if (root == NULL)
                return;
        printf("%d ", root->data);
        printf("\n");
        PrintNode(root->left_child);
        PrintNode(root->right_child);
}

int FindMin(struct BSTNode *root)
{
        if (root == NULL) {
                printf("Tree is empty.\n");
                return -10;
        }
        /*
        while (root->left_child != NULL) {
                root = root->left_child;
        }

        return root->data;*/

        //using recursion

        if (root->left_child == NULL) //base case
                return root->data;

        return FindMin(root->left_child);
}

int FindMax(struct BSTNode *root)
{
        if (root == NULL) {
                printf("Tree is empty.\n");
                return -10;
        }

        /*
        while (root->right_child != NULL) {
                root = root->right_child;
        }
        return root->data;*/

        //using recursion

        if (root->right_child == NULL) //base case
                return root->data;

        return FindMax(root->right_child);
}

int MAX(int n1, int n2)
{
        if (n1 >= n2)
                return n1;
        else
                return n2;
}

int FindHeight(struct BSTNode *root)
{
        /* This function will find the height of a tree
         * i.e height of root node in BST
         * Height of node X = No. edges in longest path from X to a leaf.
         */
        if (root == NULL)   //base condition
                return -1;

        return MAX(FindHeight(root->left_child), FindHeight(root->right_child)) + 1;
}

void Preorder(struct BSTNode *root)
{
        /*
         * <root>,<left>,<right>
         */
        if (root == NULL) //base case
                return;
        printf("%d ",root->data);
        Preorder(root->left_child);
        Preorder(root->right_child);
}

void Inorder(struct BSTNode *root)
{
        /*
         * <left>,<root>,<right>
         */
        if (root == NULL) //base case
                return;
        Inorder(root->left_child);
        printf("%d ",root->data);
        Inorder(root->right_child);
}

void Postorder(struct BSTNode *root)
{
        /*
         * <left>,<right>,<root>
         */
        if (root == NULL) //base case
                return;
        Postorder(root->left_child);
        Postorder(root->right_child);
        printf("%d ",root->data);
}

int main()
{
        struct BSTNode *root_node = NULL;
        bool ret;

        Insert(&root_node, 25);
        Insert(&root_node, 2);
        Insert(&root_node, 26);
        Insert(&root_node, 10);
        Insert(&root_node, 30);
        Insert(&root_node, 8);
        Insert(&root_node, 20);

        //search some number


        PrintNode(root_node);
        printf("\n");
        printf("pre-order:");
        Preorder(root_node);
        printf("\n");
        printf("In order:\n");
        Inorder(root_node);
        printf("\n");
        printf("post order:");
        Postorder(root_node);
        printf("\n");

        int min = FindMin(root_node);
        printf("Minimum in Tree:%d\n",min);

        int max = FindMax(root_node);
        printf("Maximum in Tree:%d\n",max);

        printf("Height of Tree:%d\n",FindHeight(root_node));

        int num;

        printf("Enter number to be searched\n");
        scanf("%d", &num);

        ret = Search(root_node, num);

        if (ret == true)
                printf("Number found.\n");
        else
                printf("Number not found.\n");

        return 0;
}

 

©2018 by memoryfaults.com. Proudly created with Wix.com