THINK FIRST·CODE LATER

← All labs

Deleting keys from a BST

Problem

Build a BST from a list of keys, then delete a second list of keys one at a time and show the resulting tree.

Rules.

  • Keys are inserted in input order into an empty tree; duplicate keys are ignored.
  • Deletion uses the three cases of the chapter. For a node with two children, copy in the in-order successor (the smallest key of the right subtree) and delete the successor from the right subtree.

Input. A line with n followed by n keys to insert; then a line with m followed by m keys to delete (n, m ≥ 0).

Output. For each key to delete, in order, one line:

delete <key>: done

or, if the key is not in the tree at that moment,

delete <key>: not found

Then three final lines:

Pre-order: <keys>
In-order: <keys>
Height: <height in edges>

An empty tree prints Pre-order: (empty), In-order: (empty) and Height: -1.

Example.

Input:
10
50 30 70 20 40 60 80 35 45 65
3
30 99 50

Output:
delete 30: done
delete 99: not found
delete 50: done
Pre-order: 60 35 20 40 45 70 65 80
In-order: 20 35 40 45 60 65 70 80
Height: 3

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d12-2-data-1.txt

10
50 30 70 20 40 60 80 35 45 65
3
30 99 50
What your program must print for d12-2-data-1.txt
delete 30: done
delete 99: not found
delete 50: done
Pre-order: 60 35 20 40 45 70 65 80
In-order: 20 35 40 45 60 65 70 80
Height: 3

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d12-2-data-1.txt

Windows PowerShell does not understand <:

Get-Content d12-2-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.