Description
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>, 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 in the BST <maximum-number> / <empty-line>
(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)
You can follow your own pseudocode for implementing these functions. For example, we know that a node can potentially be inserted at many places in a BST. But for this assignment, it is required that the node should be inserted at the leaf.
Submission
● The program you submit should output bst.txt when run.
● Follow some coding style uniformly. Provide proper comments in your code.
Evaluation
