NPTEL(WEEK-6.3)

Programming Assignment 6.3 : Binary Search Tree

Due on 2016-03-05, 23:55 IST

Write a Program to implement Binary Search tree as discussed in the Lecture.

The following methods are to be implemented in the Binary Search Tree.

1) insert(key), function which inserts a new element into the tree.

2) remove(key), function which removes the key from the Binary Search Tree

    follow these conditions to while removing the element.

          i) if the tree-node having key is a leaf node, delete that node.

ii) replace the desired tree node with its child, if that node has only one child.

iii) If the tree node having key, has two non-empty children then use its inorder - predecessor to replace the node. Inorder - predecessor for a tree node is the right most node in its left subtree.

You need to build a binary search tree by inserting elements in the given order.

Then perform insert and remove operations on that tree based on the operation specified as a character (i - insert, d - remove).

Input:

• 1st line has number of elements to be added to the Binary Search Tree (Initial number  elements - N)
• 2nd line of the input contains the elements each separated by single whitespace.
• 3rd line has number of operations to be performed (k)
• 4th line has operation, key separated by  a white space (i - insert, d - remove)

Sample Input:

4

8 7 15 2

2

i 10 d 2

Output:

The program should output the post order traversal of BST after all the given operations are performed. Separate the elements with a single whitespace. Print “NULL”(without quotes), if the tree is empty.

Output for the above Sample Input:

7 10 15 8

Constraints:

Elements in the binary Search Tree are unique.

0<=N≤ 20

0<=key<=10000 (Elements in Tree)

0<=k<=10

PROGRAM :

#include <cstdio>

using namespace std;

class binarySearchTree;

class treeNode{

/*

*with the following friend declaration

*binarySearchTree can access private members of treeNode

*/

friend class binarySearchTree;

private:

int data;

treeNode * left;

treeNode * right;

public:

treeNode(){

left=right=NULL;

}

treeNode(int key){

data=key;

left=right=NULL    ;

}

int getData(){ return data;}

void setData(int key){data=key;}

};

class binarySearchTree{

private:

treeNode * root;

public:

binarySearchTree(){root=NULL;}

void printPostOrder(treeNode * head){

if(head==NULL) return;

printPostOrder(head->left);

printPostOrder(head->right);

                printf("%d ",head->data);

}

/**As asked in the question**/

void print(){

if(root==NULL){

printf("NULL");

return;

}

printPostOrder(root->left);

printPostOrder(root->right);

printf("%d ",root->data);

}

/************************************

*inserts key in tree

*returns NULL, if the key already exists

*/

treeNode * insert(int key);

/**************************

*return 1 on success, else returns 0 if not found, -1 if empty

*removes a key from the tree

***************************/

int remove(int key);

};

int main(){

binarySearchTree bst1;

int N,val,NOp;

char op;

        scanf("%d",&N);

while(N--){

                scanf("%d",&val);

bst1.insert(val);

}

        scanf("%d",&NOp);

while(NOp--){

                scanf(" %c%d",&op,&val);

if(op == 'i'){

bst1.insert(val);

}

else if (op=='d'){

bst1.remove(val);

}

}

bst1.print();

return 0;

}

CODING:

treeNode * binarySearchTree :: insert(int key) { treeNode * temp, *prev; temp = root; prev = root; treeNode * new_node ; new_node = new treeNode(key); int flag=0; if(temp==NULL) { root = new_node; } while(temp!=NULL) { if(key < temp->data) { prev = temp; temp = temp->left; flag=1; } else if(key > temp->data) { prev = temp; temp = temp->right; flag=2; } else { printf("key already exists\n"); delete new_node; return NULL; } } if(flag==1) prev->left = new_node; else if(flag==2) prev->right = new_node; return new_node; } int binarySearchTree :: remove(int key) { treeNode * temp,*prev; temp=root; prev=NULL; int flag=0; if(root==NULL) return -1; while(temp!=NULL) { if(key < temp->data) { prev=temp; temp = temp->left; flag=1; } else if(key > temp->data) { prev=temp; temp = temp->right; flag=2; } else { break; } } if(temp==NULL) { return -1; } /* if(temp==root) { return remove(); }*/ else { if(temp->left==NULL) { if(flag==1) prev->left = temp->right; else if(flag==2) prev->right = temp->right; delete temp; return 1; } if(temp->right==NULL) { if(flag==1) prev->left = temp->left; else if(flag==2) prev->right = temp->left; delete temp; return 1; } else { treeNode * pred, *predPar; predPar = temp; pred = temp->left; while(pred->right!=NULL) { predPar = pred; pred = pred->right; } temp->data = pred->data; if(predPar->left == pred) predPar->left = pred->left; else predPar->right = pred->left; delete pred; return 1; } } }