Question

Overview The purpose of this assignment is to practice functional programming in the Racket Programming Language and to also reinforce the notion of the list as a universal data structure, by implementing various operations on binary search trees. Specification A binary search tree is a binary tree which satisfies the following invariant property: for any node X, every node in X's left subtree has a value smaller than that of X, and every node in X's right subtree has a value larger than that of X. As an example, a binary search of integers is shown in the figure below: 6 20 Figure 1: A simple binary search tree of integers. As we have seen, lists are a kind of universal data structure in the sense that every other data structure may be represented as special kind of list. As an example, in the syntax of Racket, binary search trees may be represented as a list of the form: 1 (datum left right) where: . datum is the label of the root of the tree; • left is itself a list representation of the left subtree; and . right is itself a list representation of the left subtree with the empty list ' corresponding to an empty tree. Under this schema, a binary search containing the single integer 5 would be represented by the list '(5 00); the tree comprised inserting the integers 5 and 4 into an initially empty tree would be represented by the list '(5 (4 000); and so on. Given this representation of binary search trees of integers, for this assignment you are to define the following functions in Racket: 1. empty-tree? - if T is a binary search tree of integers, then the value of the expression (empty-tree? T) is #t if and only if T is empty. 2. bst-insert - if T is a binary search tree of integers and X is an integer, then the value of the expression (bst-insert TX) is the binary search tree that results from inserting X into T.

Answer 1

1.checking BST empty or not

bool BST(node *root)

{

if (root==NULL)

return true;

else

return false;

}

2. searching an element in BST

struct node* search(struct node* root, int key)

{

    if (root == NULL || root->key == key)

       return root;

    if (root->key < key)

       return search(root->right, key);

    return search(root->left, key);

}

3.inserting an element in bst

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d \n", root->key);

        inorder(root->right);

    }

}

struct node* insert(struct node* node, int key)

{

    if (node == NULL) return newNode(key);

    if (key < node->key)

        node->left = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

    return node;

}

4.int bst_size(struct node* root)

{

if(root->left ==NULL && root->right==NULL)

return 1;

else

{

return (bst_size(root->left) +bst_size(root->right) +1);

}

}

5.bst height

int bst_height(struct node* root)

{

if(root->left == NULL && root->right==NULL)

return 0;

else

{

int a=bst_height(root->left) +1;

int b=bst_height(root->right)+1;

return max(a,b);

}

}

6.bst delete a node

struct node * minValueNode(struct node* node)

{

    struct node* current = node;

    while (current && current->left != NULL)

        current = current->left;

    return current;

}

struct node* deleteNode(struct node* root, int key)

{

    if (root == NULL) return root;

    if (key < root->key)

root->left = deleteNode(root->left, key);

    else if (key > root->key)

        root->right = deleteNode(root->right, key);

    else

    {

if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return temp;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

        struct node* temp = minValueNode(root->right);

root->key = temp->key;

        root->right = deleteNode(root->right, temp->key);

    }

    return root;

}