CS211-Assignment 2 Binary Search Tree Solved

The objective of this assignment is to implement Binary Search Tree (BST).

 

Command-line argument:

Your program should receive a file (input file) as a command line argument. 

 

Input file 
The input file will be a text file where each line will be of any of the following format:

insert <number, inorder, preorder, postorder, search <number, minimum, maximum, successor <number, predecessor <number, delete <number, where <number represents any non-negative integer. The input will be given in such a way that, at any point in time, the BST contains only distinct numbers. 

 

The output must be in a file named ‘bst.txt’. Every line in the input file must have a corresponding output line in bst.txt. The details are given below.

 

Command
Meaning
Output
insert <number
Insert <number to the BST
<number inserted
inorder
Do an inorder traversal of the BST
Sequence of numbers (separated by a white space) obtained by doing inorder traversal / <empty-line (if

BST is empty)
preorder
Do a preorder traversal of the BST
Sequence of numbers (separated by a white space) obtained by doing preorder traversal / <empty-line (if

BST is empty)
postorder
Do a post-order traversal of the BST
Sequence of numbers (separated by a white space) obtained by doing postorder traversal / <empty-line (if

BST is empty)
search <number
Search <number in the BST
<number found / <number not found
minimum
Obtain the minimum number in the BST
<minimum-number / <empty-line

(if BST is empty)
maximum
Obtain the
<maximum-number / <empty-line
 
maximum number in the BST
(if BST is empty)
successor <number
Obtain the successor of <number in the

BST
<successor / <number does not exist / successor of <number does

not exist (if <number is the maximum number)
predecessor <number
Obtain the predecessor of <number in the

BST
<predecessor / <number does not exist / predecessor of <number

does not exist (if <number is the

minimum number)

 
delete <number
Delete (if exists)

<number from the

BST
<number deleted / <number does not exist
 

The content of an example input file (on the left side) and the corresponding output file (on the right side) are given below.

 

insert 6
6 inserted
insert 9
9 inserted
insert 3
3 inserted
insert 19
19 inserted
insert 0
0 inserted
insert 5
5 inserted
inorder
0 3 5 6 9 19
preorder
6 3 0 5 9 19
search 6
6 found
search 8
8 not found
delete 10
10 does not exist
delete 9
9 deleted
insert 21
21 inserted
insert 13
13 inserted
maximum
21
minimum
0
postorder
0 5 3 13 21 19 6
successor 4
4 does not exist
predecessor 19
13
predecessor 0
predecessor of 0 does not exist
delete 0
0 deleted
delete 3
3 deleted
delete 5
5 deleted
delete 6
6 deleted
delete 19
19 deleted
delete 13
13 deleted
delete 21
21 deleted
 
delete 1
1 does not exist 
 
inorder
 
 
insert 1
1 inserted
 
inorder
1
 
 
 
 
 
 

You can follow your own pseudocode for implementing these functions. But the ‘effect’ should be the same as that discussed in the class. For example, we know that a node can potentially be inserted at many places in a BST.