Friday 30 September 2016

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

No comments:

Post a Comment