Your task is to write a function, BSTreeInsert, that inserts a given value into a BST, if it does not already exist in the BST, and returns the root of the updated BST. The insertion should be performed using normal leaf insertion. Do not rebalance the tree. If the value already exists in the BST, the function should do nothing.
Click here to download a zip of the files.
BSTree.c | Contains code for reading and printing a BST |
BSTree.h | Contains the definition of the BST data structure and function prototypes |
testBSTreeInsert.c | Contains the main function, which reads in a BST and the value to be inserted from standard input, calls BSTreeInsert, and prints out the result. |
BSTreeInsert.c | Contains BSTreeInsert, the function you must implement |
Makefile | A makefile to compile your code |
tests/ | A directory containing the inputs and expected outputs for some basic tests |
autotest | A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually. |
Your program should behave like these examples:
$ ./testBSTreeInsert
Enter the preorder traversal of the BST: 6 3 1 4 8 10
Enter value to insert: 7
BST before inserting 7:
6
/ \
/ \
3 8
/ \ \
1 4 10
BST after inserting 7:
6
/ \
/ \
/ \
3 8
/ \ / \
1 4 7 10
$ ./testBSTreeInsert
Enter the preorder traversal of the BST: 7 5 3 1
Enter value to insert: 4
BST before inserting 4:
7
/
5
/
3
/
1
BST after inserting 4:
7
/
5
/
3
/ \
1 4
$ ./testBSTreeInsert
Enter the preorder traversal of the BST:
Enter value to insert: 5
BST before inserting 5:
X
BST after inserting 5:
5
$ ./testBSTreeInsert
Enter the preorder traversal of the BST: 1 9 2 8
Enter value to insert: 5
BST before inserting 5:
1
\
9
/
2
\
8
BST after inserting 5:
1
\
9
/
2
\
8
/
5
You can test your program manually by compiling your code using make
, and then running ./testBSTreeInsert
, as shown above. After you are satisfied with your solution, you can autotest it by running ./autotest
. This will run some basic tests on your program.