Practice Exercise
Kth Smallest Value in a BST
Your task is to write a function, bstGetKth
, that takes a BST and a value k
, and returns the value at index \(k\) in the BST. The smallest value in the BST is regarded as being at index \(0\), the second smallest value is regarded as being at index \(1\), and so on.
Assumptions and Constraints
- \(k\) is between \(0\) and \(n - 1\), where \(n\) is the size of the tree
- You must not modify the given tree.
Download
While in your practice exercises directory, run the following command:
unzip /web/cs2521/practice-exercises/trees/bstGetKth/downloads/bstGetKth.zip
If you're working at home, download files.zip
by clicking on the above link and then unzip the downloaded file.
Files
bst.c | Contains code for reading and printing a BST |
bst.h | Contains the definition of the BST data structure and function prototypes |
testBstGetKth.c | Contains the main function, which reads in a BST and the value of k from standard input, calls bstGetKth and prints out the result |
bstGetKth.c | Contains bstGetKth , 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. |
Examples
./testBstGetKth Enter the preorder traversal of the BST: 3 2 1 4 5 BST: 3 / \ 2 4 / \ 1 5 Enter k: 0 For k = 0, bstGetKth returned 1 Enter k: 1 For k = 1, bstGetKth returned 2 Enter k: 2 For k = 2, bstGetKth returned 3 Enter k: 3 For k = 3, bstGetKth returned 4 Enter k: 4 For k = 4, bstGetKth returned 5 Enter k:
./testBstGetKth Enter the preorder traversal of the BST: 8 2 5 4 7 12 13 BST: 8 / \ / \ 2 12 \ \ 5 13 / \ 4 7 Enter k: 0 For k = 0, bstGetKth returned 2 Enter k: 1 For k = 1, bstGetKth returned 4 Enter k: 2 For k = 2, bstGetKth returned 5 Enter k: 3 For k = 3, bstGetKth returned 7 Enter k: 4 For k = 4, bstGetKth returned 8 Enter k: 5 For k = 5, bstGetKth returned 12 Enter k: 6 For k = 6, bstGetKth returned 13 Enter k:
./testBstGetKth Enter the preorder traversal of the BST: 7 BST: 7 Enter k: 0 For k = 0, bstGetKth returned 7 Enter k:
Testing
You can compile and test your function using the following commands:
make # compiles the program ./testBstGetKth # tests with manual input, outputs to terminal ./testBstGetKth < input-file # tests with input from a file, outputs to terminal ./testBstGetKth < tests/01.in # for example, tests with input from tests/01.in # (then manually compare with tests/01.exp)
After you have manually tested your solution, you can autotest it by running ./autotest
. This will run some basic tests on your program, as well as check for memory leaks/errors.
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.