DS LAB (II) Assignment 1 Binary Search Tree and Traversals

Binary Search Tree and Traversals

It is a binary tree with the property that the value in a node is greater than any value in a node's left sub-tree and less than any value in the node's right sub-tree.

The Operations on Binary Search Tree are:

init (T)	creates an empty Binary search tree by initializing T to NULL
insert (T, x)	inserts the value x in the proper position in the Binary search tree
search (T, x)	searches if the value x is present in the search tree
inorder (T)	displays the node using inorder traversal of binary search tree
postorder (T)	displays the node using postorder traversal of binary search tree
preorder (T)	displays the node using preorder traversal of binary search tree
delete(T, x)	Deletes node x from binary search tree

Set A

a) Implement a Binary search tree (BST) library (btree.h) with operations – create, search, insert, inorder, preorder and postorder. Write a menu driven program that performs the above operations.

b) Write a program which uses binary search tree library and counts the total nodes and total leaf nodes in the tree.
int count(T) – returns the total number of nodes from BST
int countLeaf(T) – returns the total number of leaf nodes from BST 

Set B

a) Write a C program which uses Binary search tree library and implements following function with recursion:

1. T copy(T) – create another BST which is exact copy of BST which is passed as parameter.

2. int compare(T1, T2) – compares two binary search trees and returns 1 if they are equal and 0 otherwise.

Set C
a) Write a C program which uses Binary search tree library and implements following two functions: 

int sumodd(T) – returnssum of all odd numbers from BST 

int sumeven(T) – returnssum of all even numbers from BST 

mirror(T) – converts given tree into its mirror image