Module assignment: sorted index toolkit in Python

What you will build

This assignment brings the whole module together in one program. You will build a sorted index toolkit. Think of a shop that keeps the prices of its products in a sorted list. Staff type short commands, one per line: add a price, remove a price, ask for the cheapest, ask for the next price above a given amount, count how many prices fall in a range. The program answers each command with one line of output.

The storage is your own binary search tree (BST). You must not use bisect, sorted, heapq or any other library that keeps values in order for you. The point of the exercise is to show that you can build and maintain the structure yourself, using the ideas from the four lessons of this module.

The work uses almost every technique you have learned here. Insert and search come from the first lesson, and the same loops find the minimum, the maximum, the successor and the predecessor. Delete uses the three cases and the inorder successor from the second lesson. The range count uses pruning, which is a way of skipping whole subtrees that cannot contain an answer. The height command is the recursive height from the balancing lesson. Each command is an exercise in one idea from this module, so you can judge your own progress by which commands work.

You will be graded on a scale that rewards a correct core first. A program that answers the basic commands correctly earns the first mark even if it does not handle every edge case. The rubric at the end of this page says exactly what each level looks like.

The spec

Your program reads commands from standard input until the input ends. Each command starts with a word, and some commands take one or two numbers after it. Words are separated by spaces or line breaks, so you can read the whole input with sys.stdin.read().split(). That call returns one list of words, and you walk through the list with a position counter. Read the command word first, then read exactly the numbers that command needs.

The program prints one line of output for each command that produces an answer. Commands that change the tree, such as insert and delete, print nothing. The table below lists every command.

Some rules apply to every command.

• The tree holds no duplicates. Inserting a value that is already stored changes nothing, and it prints nothing.
• Deleting a value that is not stored changes nothing, and it prints nothing.
• The values are ordinary whole numbers, which can be negative.
• next and prev work for any value, including values that are not stored in the tree. For example, if 40 and 50 are stored, next 45 prints 50.
• The count command includes both ends. If 30 and 60 are stored and the command is count 30 60, both count.
• A command word that is not in the table is an error. Print the line unknown command: followed by the word, and carry on with the next command. Do not stop the program.

The table is the complete spec. If your output differs from a sample by one space or one line break, the checker will reject it, so read the output format carefully.

Sample inputs and expected outputs

The first sample builds a small tree and then asks a range of questions. Read it as a story: each line is a request, and each answer appears in order.

Input:

insert 50
insert 30
insert 70
insert 20
insert 40
insert 60
insert 80
print
search 60
search 65
next 40
prev 40
kth 3
count 25 65
height

Expected output:

20 30 40 50 60 70 80
found
missing
50
30
40
4
3

Check two of the answers by hand, so you know what the program must do. The command next 40 asks for the smallest value greater than 40. The stored values are 20, 30, 40, 50, 60, 70 and 80, so the answer is 50. The command count 25 65 counts the stored values from 25 to 65 inclusive. Those are 30, 40, 50 and 60, which is four values.

The second sample starts with an empty tree. It checks the rules for an empty structure, which is where many programs crash.

Input:

min
insert 10
max
next 10
prev 10
kth 1
count 1 10
print
delete 10
print
height

Expected output:

empty
10
none
none
10
1
10
empty
0

The first line is empty, because nothing has been inserted yet. Then 10 is the only value, so both min and max print 10. There is no value above 10 and none below it, so next 10 and prev 10 both print none. The kth 1 command prints 10, and the count 1 10 command prints 1. After the delete, the tree is empty again, so print prints empty and height prints 0.

The third sample checks duplicates, negatives and a delete of a missing value.

Input:

insert 5
insert 5
insert 3
delete 7
print
count -10 4
next -5
kth 2

Expected output:

3 5
1
3
5

The second insert 5 is a duplicate, so it changes nothing. The delete 7 removes nothing, because 7 is not stored, and it prints nothing. The print shows only 3 and 5. The count -10 4 command finds only 3 in the range. The next -5 command finds 3, because 3 is the smallest stored value greater than -5. The kth 2 command prints 5.

Your tests should include these three samples and more. Write your own inputs for the hard cases: a delete of a node with two children, a kth with k larger than the number of values, and a long run of inserts in increasing order, which builds a chain.

Requirements checklist

Copy this list into your own notes and tick each item as you finish it. Each item can be checked by running the program on an input and reading the output.

• The program stores values only in a tree built from your own TreeNode class.
• The program does not use bisect, sorted, heapq or any other library that keeps values in order for storage.
• insert adds a value and ignores duplicates.
• delete handles a leaf, a node with one child, and a node with two children, and it ignores a value that is not stored.
• search prints found or missing, and it works on an empty tree.
• min and max print the right value, and they print empty for an empty tree.
• next and prev work for stored values and for values that are not stored.
• next and prev print none when no value exists on that side.
• kth prints the k-th smallest value, and prints none when k is less than 1 or greater than the number of values.
• count lo hi counts both ends of the range and handles a range with no values.
• height prints 0 for an empty tree and the correct height otherwise.
• print prints all values in order on one line, separated by single spaces, and prints empty for an empty tree.
• An unknown command prints unknown command: with the word, and the program carries on.
• The program reads all commands until the input ends, with no fixed count.
• Your code passes all three samples in this page, with exact output.

Step-by-step plan

Work in the order below. Each step builds on the one before, and each one can be tested on its own before you move to the next. A common mistake is to write all the commands at once and then search for bugs in all of them. Test one command at a time.

Step 1: the node and the insert. Write the TreeNode class with a value and two links, then write the recursive insert from the first lesson. Test it by inserting a few values and printing the inorder walk. The output must be sorted.

Step 2: print and height. Write the inorder walk that collects values into a list, then use it to build the print output. Write the recursive height. Test an empty tree first, then a chain, then a balanced tree.

Step 3: search, min and max. Write the loop search from the first lesson. Write min and max by walking left and right until the link is None. Remember to handle the empty tree before you touch any node.

Step 4: next and prev. Use the root walk from the second lesson. For next, keep the last node where you went left. For prev, keep the last node where you went right. Test with values that are stored and values that are not stored, and with the largest and smallest values in the tree.

Step 5: kth and count. For kth, collect the inorder list and read the entry at position k minus 1, after checking that k is in range. For count, write the pruned version: if a node's value is below lo, skip its left subtree, and if it is above hi, skip its right subtree.

Step 6: delete. Write the delete from the second lesson with its three cases. Test each case separately on a small tree, and then print the inorder walk after each delete.

Step 7: the command loop. Read the command word from the list of words, then use a match statement on it (Python 3.10 or newer). Each case reads its numbers and prints its line. Add the case _ branch for unknown words. Do this last, because it only connects the parts you have already tested.

Step 8: test the edges. Run the three samples. Then run your own tests, with an empty tree, a single value, duplicates, negative numbers and the same value inserted and deleted several times.

Grading rubric

The mark is based on what the program does on a set of hidden inputs, and on the quality of your code. The levels below describe what each mark looks like in practice.

60 percent: the core works. The program reads commands until the input ends. insert, search, print, min, max and height give correct output on ordinary inputs. delete works for at least a leaf and a node with one child. The tree stays a BST after every command, which you can check with print. The program may fail on the edge cases of next, prev, kth and count, or on empty-tree inputs.

80 percent: the whole spec works on ordinary inputs. Everything in the table works, including next, prev, kth and count. Delete handles a node with two children correctly, and the duplicate and missing-value cases print nothing and change nothing. The empty tree is handled for every command, and each none and empty answer appears exactly where the spec says. The code is organised into small functions, one per idea, rather than one long block in the main part of the file.

100 percent: the whole spec works on every input, and the code is clean. The program passes the hidden tests, including large inputs such as a few thousand inserts in increasing order and then a query for each value. The count command prunes subtrees, so that it does not visit every node when the range is small. The kth command does not rebuild the whole list when it is not needed, or it does so with a clear reason. The code has no unused variables, no commented-out code, and each function has one clear job. The program prints every line with exact spacing and line breaks.

A note on large inputs. A chain of several hundred values makes the recursive insert, inorder walk and height go deep. Python stops a call chain at about 1000 calls by default, and the stopping point is a RecursionError. A chain of about 1000 values or more can hit that limit. The 100 percent mark does not require a special workaround for that size. A comment in your code that states the depth limit is good practice.

Hints

Each hint below is hidden. Open one only when you are stuck on that step, and try the step again before you open the next hint.

Reference solution

The solution below follows the spec and the steps above. It is one file, with one function for each idea. Try the assignment on your own first. Compare your version with this one only after you have tested your program on the three samples and your own edge cases, so that you learn from the differences.

import sys
 
 
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
 
def insert(n, v):
    if n is None:
        return TreeNode(v)
    if v < n.val:
        n.left = insert(n.left, v)
    elif v > n.val:
        n.right = insert(n.right, v)
    return n
 
 
def min_node(n):
    while n.left is not None:
        n = n.left
    return n
 
 
def max_node(n):
    while n.right is not None:
        n = n.right
    return n
 
 
def delete(n, v):
    if n is None:
        return None
    if v < n.val:
        n.left = delete(n.left, v)
    elif v > n.val:
        n.right = delete(n.right, v)
    else:
        if n.left is None:
            return n.right
        if n.right is None:
            return n.left
        s = min_node(n.right)
        n.val = s.val
        n.right = delete(n.right, s.val)
    return n
 
 
def search(n, v):
    while n is not None:
        if v == n.val:
            return True
        n = n.left if v < n.val else n.right
    return False
 
 
def next_value(n, v):
    best = None
    while n is not None:
        if v < n.val:
            best = n.val
            n = n.left
        else:
            n = n.right
    return best
 
 
def prev_value(n, v):
    best = None
    while n is not None:
        if v > n.val:
            best = n.val
            n = n.right
        else:
            n = n.left
    return best
 
 
def height(n):
    if n is None:
        return 0
    return 1 + max(height(n.left), height(n.right))
 
 
def inorder(n, out):
    if n is None:
        return
    inorder(n.left, out)
    out.append(n.val)
    inorder(n.right, out)
 
 
def count_range(n, lo, hi):
    if n is None:
        return 0
    if n.val < lo:
        return count_range(n.right, lo, hi)
    if n.val > hi:
        return count_range(n.left, lo, hi)
    return 1 + count_range(n.left, lo, hi) + count_range(n.right, lo, hi)
 
 
def answer(value):
    return "none" if value is None else str(value)
 
 
def main():
    words = sys.stdin.read().split()
    pos = 0
    root = None
    lines = []
 
    def take():
        nonlocal pos
        text = words[pos]
        pos += 1
        return int(text)
 
    while pos < len(words):
        cmd = words[pos]
        pos += 1
        match cmd:
            case "insert":
                root = insert(root, take())
            case "delete":
                root = delete(root, take())
            case "search":
                lines.append("found" if search(root, take()) else "missing")
            case "min":
                lines.append("empty" if root is None else str(min_node(root).val))
            case "max":
                lines.append("empty" if root is None else str(max_node(root).val))
            case "next":
                lines.append(answer(next_value(root, take())))
            case "prev":
                lines.append(answer(prev_value(root, take())))
            case "kth":
                k = take()
                values = []
                inorder(root, values)
                lines.append(str(values[k - 1]) if 1 <= k <= len(values) else "none")
            case "count":
                lo = take()
                hi = take()
                lines.append(str(count_range(root, lo, hi)))
            case "height":
                lines.append(str(height(root)))
            case "print":
                values = []
                inorder(root, values)
                lines.append(" ".join(str(v) for v in values) if values else "empty")
            case _:
                lines.append("unknown command: " + cmd)
 
    if lines:
        print("\n".join(lines))
 
 
main()

Here is how the solution handles the parts that are easy to get wrong. The search, next and prev functions use loops, so they use no extra calls. count_range skips a subtree when the node is outside the range, which is the pruning from step 5. The kth command collects the inorder list and checks k first, so an out-of-range k never reads past the end of the list. The output lines are collected in one list and printed once at the end, which is faster than printing each line as it is made.

The delete function is the one from the second lesson, with the copy of the successor value. The results of next_value and prev_value are None when there is no answer, and the output step turns None into the word none.

The kth command runs a full inorder walk for each query, so its cost is O(n) per command. That is acceptable for this exercise. A faster version would keep a count of the nodes in each subtree, as the next lessons of this module show.

Before you submit

Run your program on the three samples in this page and compare the output with the expected output, line by line. Then run it on an input you write yourself that covers an empty tree, a delete of a node with two children, and a kth with k larger than the tree. Check each output by hand against the table in the spec before you trust the program.