For this assignment you will be implementing a few simple binary search tree operations. Specifically, your program will take two arguments (an input file and an integer number) and it will output a single value (the rank of the input number).

This assignment is worth a total of 20 points. You will receive 8 points if your program outputs the correct values (this will be checked by the autograder). To receive the other 12 points you will need to do the following:

ensure that all group members have their names at the top of the file (under the shebang for Python programs), and

implement a program that solves the problem using binary search tree (so, if you were to implement this using a sorted array you would still get several points).

The input file

Your programs will read a simple input file, the name of which will be provided as the first program argument. The file will include a list of unique (not duplicates) integer numbers:

4

2

1

3

6

5

7

Each line in the file is a key value that you will insert into your binary search tree. You do not need to worry about balancing the tree for this assignment. You should simply insert each value as a leaf node.

For example, the list above would be built up as follows:

(1) 4

(2) 4

/

2

(3) 4

/

2

/

1

(4) 4

/

2

/ \

1 3

(5) 4

/ \

2 6

/ \

1 3

(6) 4

/ \

2 6

/ \ /

1 3 5

(7) 4

/ \

2 6

/ \ / \

1 3 5 7

If the input file was in a different order (like 2 1 3 4 5 6 7) your tree could easily look like this (and it would be fine):

2

/ \

1 3

\

4

\

5

\

6

\

7

Your program

Your file should be named bst_rank.{py,cpp,rs}. Again, you are required to write the names of all partners in comments at the top of the file.

You should start by opening the input file and reading its contents into a BST that holds integers as key values. The examples at this website will be helpful in showing you how to write a BST in Python or C++ (sorry, no examples in Rust just yet). Since our problem is a bit different, youll need to augment the Node class a bit. For example, mine looks like this in python:

class Node:

def __init__(self, key):

self.key = key

self.left = None

self.right = None

self.size = 1 # I added this member variable

The member variable size will need to be updated by the function that you use to build your BSTs. Pages 8 and 9 of our lectures slides should give you an idea about how you can use the size member variable.

Next, you will need to write a function for finding the rank of a given number. For this assignment, rank is defined as the number of keys in the BST that are less than the given number. This problem can be thought of as the inverse of the selection problem. See the example below for the expected output of the example input.

Example

Example input_file.txt:

4

2

1

3

6

5

7

Example program interaction:

> ./bst_rank.py input_file.txt 0

0

> ./bst_rank.py input_file.txt 1

0

> ./bst_rank.py input_file.txt 2

1

> ./bst_rank.py input_file.txt 3

2

> ./bst_rank.py input_file.txt 4

3

> ./bst_rank.py input_file.txt 5

4

> ./bst_rank.py input_file.txt 6

5

> ./bst_rank.py input_file.txt 7

6

> ./bst_rank.py input_file.txt 8

7

> ./bst_rank.py input_file.txt 1231

7