Showing posts with label Module 4. Show all posts
Showing posts with label Module 4. Show all posts

Friday 30 September 2016

Height of Binary Search Tree

Height of the Binary Search Tree


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

struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE , NODE );
int max(int a, int b);
int height(NODE root);

void insert(NODE root, NODE newnode)
{
    /*Note: if newnode->data ==  root->data it will be skipped. No duplicate nodes are allowed */
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}
int max(int a, int b)
{
            return (a>b)?a:b;
}

int height(NODE root)
{
            if(root == NULL)
                        return 0;
            else
                        return     1 + max( height(root->lchild), height(root->rchild) );
}

void main()
{
            int val, i,n, ht;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d", &n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }
            ht = height(root);
            printf("\nThe Height of tree is: %d", ht);
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
 The Height of tree is: 4
Posted by at No comments:
Labels: ,

Binary Search Tree: Find Minimum Value

Find the Minimum Valued node in  the Binary Search Tree


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;

 NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

 void insert(NODE root, NODE newnode)
{
             /*Note: if newnode->data ==  root->data it will be skipped. 
             No duplicate nodes are allowed */
            
             if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}

void minimum(NODE root)
{
            NODE cur;
            if(root == NULL)
            {
                        printf("\nBST not created");               return;
            }
            cur = root;
            while(cur->lchild!=NULL)
                        cur = cur->lchild;
            printf("\nMinimum value in a tree is: %d", cur->data);
}

void main()
{
            int val, i,n;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }
            if(root == NULL)
                        printf("\nTree is not created");
            else
            {
                        minimum(root);          //Function to find min valued node
            }
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Minimum value in a tree is: 2
Posted by at No comments:
Labels: , ,

Binary Search Tree: Find Maximum Value

Find the Maximum Valued node in  the Binary Search Tree


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;

NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
    /*Note: if newnode->data ==  root->data it will be skipped. No duplicate nodes are allowed */
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}
void maximum(NODE root)
{
            NODE cur;
            if(root== NULL)
            {
                        printf("\nBST not created");         return;
            }
            cur = root;
            while(cur->rchild != NULL)
                        cur = cur->rchild;
            printf("\nMaximum value in a tree is: %d", cur->data);
}

void main()
{
            int val, i,n;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d",&n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }
            if(root == NULL)
                        printf("\nTree is not created");
            else
            {
                        maximum(root);          //Function to find max valued node
            }
}

Output:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2
Maximum value in a tree is: 24


Posted by at No comments:
Labels: , ,

Binary Search Tree: Search for key element

Binary Search Tree:  Search for key element


#include<stdio.h>
#include<stdlib.h>
struct BST
{
            int data;
            struct BST *lchild;
            struct BST *rchild;
};
typedef struct BST * NODE;
NODE get_node()
{
            NODE temp;
            temp = (NODE) malloc(sizeof(struct BST));
            temp->lchild = NULL;
            temp->rchild = NULL;
            return temp;
}

void insert(NODE root, NODE newnode)
{
            if (newnode->data < root->data)
            {
                        if (root->lchild == NULL)
                                    root->lchild = newnode;
                        else
                                    insert(root->lchild, newnode);
            }
            if (newnode->data > root->data)
            {
                        if (root->rchild == NULL)
                                    root->rchild = newnode;
                        else
                                    insert(root->rchild, newnode);
            }
}
void search(NODE root, int key)
{
            NODE cur;
            if(root == NULL)
            {
                        printf("\nBST is empty.");
                        return;
            }
            cur = root;
            while (cur != NULL)
            {
                        if (cur->data == key)
                        {
                                    printf("\nKey element %d is present in BST", cur->data);
                                    return;
                        }
                        if (key < cur->data)
                                    cur = cur->lchild;
                        else
                                    cur = cur->rchild;
            }
            printf("\nKey element %d is not found in the BST", key);
}
void main()
{
            int val, i, n, key;
            NODE root = NULL, newnode;
            printf("\nEnter the number of elements: ");
            scanf("%d", &n);
            for(i=1;i<=n;i++)
            {
                        newnode = get_node();
                        printf("\nEnter The node value: ");
                        scanf("%d", &val);
                        newnode->data = val;
                        if (root == NULL)
                                    root = newnode;
                        else
                                    insert(root, newnode);
            }
           
             /*Search for a given key in BST*/
            printf("\nEnter Element to be searched: ");
            scanf("%d", &key);
            search(root, key);
}
Case 1:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2

Enter Element to be searched: 66
Key element 66 is not found in the BST


Case 2:
Enter the number of elements: 12
Enter The node value: 6
Enter The node value: 9
Enter The node value: 5
Enter The node value: 2
Enter The node value: 8
Enter The node value: 15
Enter The node value: 24
Enter The node value: 14
Enter The node value: 7
Enter The node value: 8
Enter The node value: 5
Enter The node value: 2

Enter Element to be searched: 5
Key element 5 is present in BST
Posted by at No comments:
Labels: ,
Subscribe to: Posts (Atom)