Module assignment: BST toolkit

Why this assignment

This assignment puts every lesson of the module into one program. You will insert and delete values, search for them, find successors and predecessors, measure the height, answer k-th queries, and print the tree in order. Each part uses an idea from one of the lessons: the rule and the search from lesson 1, the three delete cases and postorder freeing from lesson 2, the successor walk and the stack-based k-th query from lesson 3, and the effect of shape on height from lesson 4. The stretch part at the end asks you to use the AVL rotations from lesson 5.

The program you write is a small ordered set. It reads commands from the Input box, one per line, and prints the answers. A real service that keeps a sorted list of values, such as a leaderboard or a list of free time slots, needs the same operations. Building it yourself makes the trade-offs visible: you will see the height rise on sorted input and fall again after a balanced rebuild.

Work through the spec, then the requirements list, then the starter. Only after you have a working version should you open the hints or the reference solution.

The specification

The first line of input is a number q, the count of commands that follow. Each of the next q lines holds one command. The commands use capital letters and are case-sensitive. The first word is the command name, and some commands take one number after it.

Command	What it does	What it prints
`I x`	Insert x. If x is already stored, do nothing.	Nothing
`D x`	Delete x. If x is not stored, do nothing.	Nothing
`C x`	Check whether x is stored.	`yes` or `no`
`S x`	Find the smallest stored value strictly greater than x.	The value, or `none`
`P x`	Find the largest stored value strictly less than x.	The value, or `none`
`MIN`	Find the smallest stored value.	The value, or `empty`
`MAX`	Find the largest stored value.	The value, or `empty`
`H`	Measure the height. An empty tree has height 0.	The number
`K k`	Find the k-th smallest stored value, where k = 1 is the smallest.	The value, or `none` if k is less than 1 or larger than the number of values
`PRINT`	List all stored values in increasing order.	The values separated by single spaces, or `empty`

Every value is an integer from 1 to 1,000,000. The number of commands is at most 1,000. Every value is positive, so the number -1 never appears as a real value, and you may use it as a "not found" signal inside your code.

Two rules matter for the height. First, when a node has two children and you delete it, you copy its inorder successor into it and delete the successor from the right subtree, as lesson 2 shows. Second, insert always places a new value according to the BST rule, with no balancing. The height that H prints depends on both rules, so do not use the predecessor instead of the successor in this assignment. The checker expects the successor rule.

Each command that prints produces one line of output. Commands that do not print produce nothing. The program must end normally after the last command.

Sample 1

The first sample inserts seven values, adds a duplicate, asks four questions and prints the tree. Type this into the Input box:

14
I 50
I 30
I 70
I 20
I 40
I 60
I 80
I 30
C 40
S 40
P 60
K 3
D 30
PRINT

The correct output is:

yes
50
50
40
20 40 50 60 70 80

Check each line. The first I 30 is a duplicate, so nothing changes. C 40 finds 40 and prints yes. The smallest value greater than 40 is 50, so S 40 prints 50. The largest value less than 60 is 50, so P 60 prints 50. The third smallest of 20, 30, 40, 50, 60, 70, 80 is 40, so K 3 prints 40. After D 30, the stored values are 20, 40, 50, 60, 70 and 80, which PRINT lists in order.

Sample 2

The second sample checks the empty tree and the bad-input answers. Type this into the Input box:

6
MIN
MAX
H
PRINT
K 1
P 5

The correct output is:

empty
empty
0
empty
none
none

The tree has no values, so MIN, MAX and PRINT say empty, and the height is 0. K 1 asks for the smallest value, and there is none, so it prints none. P 5 asks for the largest value less than 5, and there is none.

Sample 3

The third sample checks the height and the two-child delete. Type this into the Input box:

14
I 8
I 3
I 10
I 1
I 6
I 14
I 4
I 7
H
D 3
H
D 8
H
PRINT

The correct output is:

4
4
4
1 4 6 7 10 14

Start with the first H. The tree is 8 with left subtree 3 (left child 1, right subtree 6 with children 4 and 7) and right subtree 10 with right child 14. The longest path is 8, 3, 6, 4, which has four nodes. Then D 3 deletes a node with two children, so 3 is replaced by its successor, which is 4. The longest path is now 8, 4, 6, 7, which still has four nodes. The last delete, D 8, removes the root. Its successor is 10, which becomes the root. The longest path is 10, 4, 6, 7, which again has four nodes. If your program prints 3 for any of these, check that your two-child delete uses the successor.

Requirements checklist

Copy this list into your notes and tick each item when you have tested it. The grader checks the same items.

The starter program

The starter below contains the command loop already. It reads the commands and calls ten functions that you write. Each function currently returns a placeholder value, so the output is wrong until you fill them in. That is expected. Press Run once to see what the placeholders print. For sample 1 the starter prints:

no
none
none
none
empty

Your job is to replace each TODO body. The functions have clear names, and you can test each one as you finish it.

C++ · editable

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// TODO 1: insert x. If x is already stored, do nothing. Return the root.
Node* insert(Node* root, int x) {
    return root;
}

// TODO 2: delete x if it is stored, using the three cases. Return the root.
Node* erase(Node* root, int x) {
    return root;
}

// TODO 3: return true if x is stored.
bool contains(Node* root, int x) {
    return false;
}

// TODO 4: return the node holding the smallest value greater than x, or nullptr.
Node* successor(Node* root, int x) {
    return nullptr;
}

// TODO 5: return the node holding the largest value less than x, or nullptr.
Node* predecessor(Node* root, int x) {
    return nullptr;
}

// TODO 6: return the height. An empty tree has height 0.
int height(Node* root) {
    return 0;
}

// TODO 7: return the k-th smallest value (k starts at 1), or -1 if there are fewer than k values.
int kthSmallest(Node* root, int k) {
    return -1;
}

// TODO 8: add every stored value to out, in sorted order.
void collect(Node* root, vector<int>& out) {
}

// TODO 9: return the node with the smallest value, or nullptr for an empty tree.
Node* minNode(Node* root) {
    return nullptr;
}

// TODO 10: return the node with the largest value, or nullptr for an empty tree.
Node* maxNode(Node* root) {
    return nullptr;
}

int main() {
    int q;
    cin >> q;
    Node* root = nullptr;
    while (q--) {
        string cmd;
        cin >> cmd;
        if (cmd == "I") {
            int x;
            cin >> x;
            root = insert(root, x);
        } else if (cmd == "D") {
            int x;
            cin >> x;
            root = erase(root, x);
        } else if (cmd == "C") {
            int x;
            cin >> x;
            cout << (contains(root, x) ? "yes" : "no") << "\n";
        } else if (cmd == "S") {
            int x;
            cin >> x;
            Node* s = successor(root, x);
            if (s) cout << s->val << "\n";
            else cout << "none\n";
        } else if (cmd == "P") {
            int x;
            cin >> x;
            Node* p = predecessor(root, x);
            if (p) cout << p->val << "\n";
            else cout << "none\n";
        } else if (cmd == "MIN") {
            Node* m = minNode(root);
            if (m) cout << m->val << "\n";
            else cout << "empty\n";
        } else if (cmd == "MAX") {
            Node* m = maxNode(root);
            if (m) cout << m->val << "\n";
            else cout << "empty\n";
        } else if (cmd == "H") {
            cout << height(root) << "\n";
        } else if (cmd == "K") {
            int k;
            cin >> k;
            int v = kthSmallest(root, k);
            if (v != -1) cout << v << "\n";
            else cout << "none\n";
        } else if (cmd == "PRINT") {
            vector<int> out;
            collect(root, out);
            if (out.empty()) {
                cout << "empty\n";
            } else {
                for (size_t i = 0; i < out.size(); i++) {
                    if (i) cout << " ";
                    cout << out[i];
                }
                cout << "\n";
            }
        }
    }
    return 0;
}

Two details in the starter are worth noticing. The main function stores the return value of insert and erase back into root, because either call can change the root. And the K branch treats -1 as the "not found" signal, which is safe because every real value is positive.

Grading rubric

The grade depends on how many commands produce correct output across the samples and a set of hidden inputs. The three levels below describe what each solution looks like. Read them before you start, so you know what to aim for.

A 60% solution compiles and handles the basic commands. Insert, C, PRINT, MIN and MAX are correct, and deleting a leaf or a node with one child works. An empty tree does not crash. Sample 2 passes. The two-child delete may be wrong, and H, K, S and P may be missing or wrong. Typical symptoms are a crash on D of a node with two children, or a PRINT that lists a value twice after a delete.

An 80% solution adds the two-child delete with the successor rule, plus S, P and K. Sample 1 passes exactly. The height command may still be wrong on some hidden inputs, which usually means the delete does not copy the successor, or the height function counts edges instead of nodes. The program may still leak memory.

A 100% solution passes all three samples and every hidden input. H is correct after deletes, K handles out-of-range values, duplicates are ignored everywhere, and the program frees its memory. Running the program under -fsanitize=address,undefined prints nothing extra, and the program exits with code 0.

Your own testing matters as much as the grade. Write small inputs by hand and predict the output on paper before you run them. The samples cover the basics. Your job is to find the cases they miss, such as deleting the root with two children, asking for the successor of the largest value, and running K with k equal to 0.

Step-by-step hints

Open one hint at a time. Each hint gives a direction, not the full code. Try the step before you open the next hint.

Hint 1: insert and contains

Copy the recursive insert from lesson 1. It ignores equal values, which gives you the duplicate rule for free. For contains, copy the iterative search from lesson 1, and return true when the target equals the node's value.

Hint 2: erase

Copy the erase function from lesson 2. It has the three cases in order: no left child, no right child, then two children. The two-child branch uses the leftmost node of the right subtree, which is minNode(root->right). Your minNode from TODO 9 can serve that role.

Hint 3: successor and predecessor

Use the walk from lesson 3. For the successor, record the node whenever you move left, because that node is larger than the target. For the predecessor, record the node whenever you move right, because that node is smaller than the target. Both walks return the last candidate they recorded.

Hint 4: height and k-th

The height is the recursive function from lesson 1: an empty tree returns 0, and a node returns 1 plus the larger of its two subtree heights. For the k-th value, use the recursive version from lesson 3. Pass k by reference, count down as you visit each node in order, and return the value when the count reaches 0. Return -1 when the walk ends without reaching 0. The main function passes a copy of k, so the K command still works if you call it twice.

Hint 5: collect and PRINT

The collect function is an inorder walk: left subtree, then the node, then the right subtree. Add each value to out with push_back. main already prints the values with spaces between them, so you do not need to format the output in collect.

Testing your program

Compile with warnings turned on and the sanitizers enabled. The two flags catch most memory mistakes before they become wrong answers:

g++ -std=c++17 -Wall -Wextra -g -fsanitize=address,undefined -o toolkit toolkit.cpp

Run it on each sample. Then write a small input with a single delete, predict the output, and compare. Check that your PRINT line has no trailing space. A trailing space can fail a strict comparison, and main in the starter avoids it by printing a space before every value except the first.

If the sanitizer reports a heap-use-after-free, look for a node you read after delete. If it reports a leak, check that you free every node before the program ends, which is what the postorder function in lesson 2 does. Add a call to it at the end of main, after the command loop.

Reference solution

Read this only after you have tried the assignment. It is one correct version of the program, written in the same style as the lessons. Your version may use different names and different helper functions, and it can still be correct. The checker tests the output, not the code.

Reference solution

C++ · editable

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int x) {
    if (!root) return new Node(x);
    if (x < root->val) root->left = insert(root->left, x);
    else if (x > root->val) root->right = insert(root->right, x);
    return root;                          // equal: already stored, do nothing
}

Node* minNode(Node* root) {
    if (!root) return nullptr;
    while (root->left) root = root->left;
    return root;
}

Node* maxNode(Node* root) {
    if (!root) return nullptr;
    while (root->right) root = root->right;
    return root;
}

Node* erase(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->val) {
        root->left = erase(root->left, key);
    } else if (key > root->val) {
        root->right = erase(root->right, key);
    } else {
        if (!root->left) {
            Node* r = root->right;
            delete root;
            return r;
        }
        if (!root->right) {
            Node* l = root->left;
            delete root;
            return l;
        }
        Node* succ = minNode(root->right);
        root->val = succ->val;
        root->right = erase(root->right, succ->val);
    }
    return root;
}

bool contains(Node* root, int x) {
    while (root) {
        if (x == root->val) return true;
        root = (x < root->val) ? root->left : root->right;
    }
    return false;
}

// Smallest value greater than x, or nullptr.
Node* successor(Node* root, int x) {
    Node* best = nullptr;
    while (root) {
        if (x < root->val) {
            best = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return best;
}

// Largest value less than x, or nullptr.
Node* predecessor(Node* root, int x) {
    Node* best = nullptr;
    while (root) {
        if (x > root->val) {
            best = root;
            root = root->right;
        } else {
            root = root->left;
        }
    }
    return best;
}

int height(Node* root) {
    if (!root) return 0;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

// k counts down as nodes are passed in order. Returns the value, or -1 if not found.
int kthSmallest(Node* n, int& k) {
    if (!n) return -1;
    int found = kthSmallest(n->left, k);
    if (found != -1) return found;
    k--;
    if (k == 0) return n->val;
    return kthSmallest(n->right, k);
}

void collect(Node* n, vector<int>& out) {
    if (!n) return;
    collect(n->left, out);
    out.push_back(n->val);
    collect(n->right, out);
}

void freeTree(Node* n) {
    if (!n) return;
    freeTree(n->left);
    freeTree(n->right);
    delete n;
}

int main() {
    int q;
    cin >> q;
    Node* root = nullptr;
    while (q--) {
        string cmd;
        cin >> cmd;
        if (cmd == "I") {
            int x;
            cin >> x;
            root = insert(root, x);
        } else if (cmd == "D") {
            int x;
            cin >> x;
            root = erase(root, x);
        } else if (cmd == "C") {
            int x;
            cin >> x;
            cout << (contains(root, x) ? "yes" : "no") << "\n";
        } else if (cmd == "S") {
            int x;
            cin >> x;
            Node* s = successor(root, x);
            if (s) cout << s->val << "\n";
            else cout << "none\n";
        } else if (cmd == "P") {
            int x;
            cin >> x;
            Node* p = predecessor(root, x);
            if (p) cout << p->val << "\n";
            else cout << "none\n";
        } else if (cmd == "MIN") {
            Node* m = minNode(root);
            if (m) cout << m->val << "\n";
            else cout << "empty\n";
        } else if (cmd == "MAX") {
            Node* m = maxNode(root);
            if (m) cout << m->val << "\n";
            else cout << "empty\n";
        } else if (cmd == "H") {
            cout << height(root) << "\n";
        } else if (cmd == "K") {
            int k;
            cin >> k;
            int copy = k;
            int v = (k >= 1) ? kthSmallest(root, copy) : -1;
            if (v != -1) cout << v << "\n";
            else cout << "none\n";
        } else if (cmd == "PRINT") {
            vector<int> out;
            collect(root, out);
            if (out.empty()) {
                cout << "empty\n";
            } else {
                for (size_t i = 0; i < out.size(); i++) {
                    if (i) cout << " ";
                    cout << out[i];
                }
                cout << "\n";
            }
        }
    }
    freeTree(root);
    return 0;
}

The reference solution passes all three samples. It was also checked against a separate model on 300 random command lists, mixing every command, with no differences and no sanitizer reports. The main parts to study are the two-child delete, which copies the successor, and the copy variable in K, which stops the k-th walk from changing the value the command read.

Stretch: keep the tree balanced

The basic program can become a chain. Insert the values 1 to 1,000 in order, and then H prints 1000. Your stretch task is to make the same program stay short on sorted input.

Start from the AVL insert of lesson 5. Add the rotateLeft and rotateRight functions, a height field in each node, and the rebalancing check on the way back up. Keep the delete as it is, and check that the height stays small for inserts alone. A balanced version prints different H values from the samples, so keep the basic program as a separate file for grading. In your own notes, explain in one paragraph why the two versions print different heights for the same commands.

A harder stretch is to add a V command that checks the BST rule on the whole tree, using the bounds method from lesson 3. It prints valid or invalid. You can test it on a tree that you break on purpose by editing a value in memory, which shows that the check catches the error.

Run this short program to see the problem for yourself. It inserts the values 1 to 1000 in order into a plain tree and prints the height. Nothing is typed into the Input box.

C++ · editable

The output is:

height after 1000 sorted inserts: 1000

The height equals the number of values, so the tree is a chain. Your balanced version should print a number close to 10 for the same input, because 2 to the power 10 is 1024.

What you now know

A working ordered set needs insert, search, delete, successor, height and k-th queries, and each query follows one path or one walk.
The two-child delete copies the successor, and then deletes the successor from the right subtree.
Sorted input makes the height grow to n, and balancing keeps it near log n.
Test with predicted outputs on paper, and let the sanitizer find memory mistakes.

Module assignment: BST toolkit

Why this assignment

The specification

Sample 1

Sample 2

Sample 3

Requirements checklist

The starter program

Grading rubric

Step-by-step hints

Testing your program

Reference solution

Stretch: keep the tree balanced

What you now know

Stuck? Ask the tutor