Your task is to write a function, BSTreeGetKth, that returns the k'th smallest value in the given BST. You can assume that k is between 0 and N - 1, where N is the size of the tree.
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 |
| testBSTreeGetKth.c | Contains the main function, which reads in a BST from standard input, calls BSTreeGetKth for each value of k read in, and prints out the results. |
| BSTreeGetKth.c | Contains BSTreeGetKth, 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:
$ ./testBSTreeGetKth
Enter the preorder traversal of the BST: 3 2 1 4 5
Tree:
3
/ \
2 4
/ \
1 5
Enter k: 0
For k = 0, BSTreeGetKth returned 1
Enter k: 1
For k = 1, BSTreeGetKth returned 2
Enter k: 2
For k = 2, BSTreeGetKth returned 3
Enter k: 3
For k = 3, BSTreeGetKth returned 4
Enter k: 4
For k = 4, BSTreeGetKth returned 5
Enter k: (Ctrl + D)
$ ./testBSTreeGetKth
Enter the preorder traversal of the BST: 8 2 5 4 7 12 13
Tree:
8
/ \
/ \
2 12
\ \
5 13
/ \
4 7
Enter k: 0
For k = 0, BSTreeGetKth returned 2
Enter k: 1
For k = 1, BSTreeGetKth returned 4
Enter k: 2
For k = 2, BSTreeGetKth returned 5
Enter k: 3
For k = 3, BSTreeGetKth returned 7
Enter k: 4
For k = 4, BSTreeGetKth returned 8
Enter k: 5
For k = 5, BSTreeGetKth returned 12
Enter k: 6
For k = 6, BSTreeGetKth returned 13
Enter k: (Ctrl + D)
$ ./testBSTreeGetKth
Enter the preorder traversal of the BST: 7
Tree:
7
Enter k: 0
For k = 0, BSTreeGetKth returned 7
Enter k: (Ctrl + D)
You can test your program manually by compiling your code using make, and then running ./testBSTreeGetKth, 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.