Illustrate the algorithm for Binary search tree with example.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

Binary Search Tree

A binary search tree (BST) is a binary tree that is either empty or in which every node contains a key (value) and satisfies the following conditions:

  • All keys in the left sub-tree of the root are smaller than the key in the root node
  • All keys in the right sub-tree of the root are greater than the key in the root node
  •  The left and right sub-trees of the root are again binary search trees

Example:

Given the following sequence of numbers,

        14, 4, 15, 3, 9, 14, 18

The following binary search tree can be constructed:

Algorithm to search the element in BST

void BinSearch(struct bnode *root , int key)
{
    if(root == NULL)
    {
        printf(“The number does not exist”);
        exit(1);
    }
    else if (key == root->info)
    {
        printf(“The searched item is found”):
    }

    else if(key < root->info)
        return BinSearch(root->left, key);
    else
        return BinSearch(root->right, key);

}

Algorithm to insert the element in BST

void insert(struct bnode *root, int item)
{
    if(root=NULL)
    {
        root=(struct bnode*)malloc (sizeof(struct bnode));
        root->left=root->right=NULL;
        root->info=item;
    }
    else
    {
        if(item<root->info)
            root->left=insert(root->left, item);
        else
            root->right=insert(root->right, item);
    }
}

E.g.

User Loaded Image | CSIT Guide

Algorithm to delete the element in BST

struct bnode *delete(struct bnode *root, int item)
{
    struct bnode *temp;

    if(root==NULL)
    {
        printf(“Empty tree”);
        return;
    }
    else if(item<root->info)
         root->left=delete(root->left, item);
    else if(item>root->info)
         root->right=delete(root->right, item);
    else if(root->left!=NULL &&root->right!=NULL)   //node has two child
    {
        temp=find_min(root->right);
        root->info=temp->info;
        root->right=delete(root->right, root->info);
    }
    else
    {
        temp=root;
        if(root->left==NULL)
             root=root->right;
        else if(root->right==NULL)
             root=root->left;
        free(temp);
    }
    return(temp);
}

Finding minimum element function:

struct bnode *find_min(struct bnode *root)
{
    if(root==NULL)
         return0;
    else if(root->left==NULL)
         return root;
    else
         return(find_min(root->left));
}

E.g.

1.Deleting leaf Node

User Loaded Image | CSIT Guide

2.Deleting node with right child

User Loaded Image | CSIT Guide

3.Deleting node with left child

User Loaded Image | CSIT Guide

4.Deleting a node having both right and left child

User Loaded Image | CSIT Guide

User Loaded Image | CSIT Guide

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .