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

Your solution

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.

import java.util.Scanner;

class IntBST {
    private static class Node {
        int key;
        Node left, right;
        Node(int key) { this.key = key; }
    }

private Node root;

void insert(int key) { root = insert(root, key); }

private Node insert(Node n, int key) {
        if (n == null) return new Node(key);
        if (key < n.key) n.left = insert(n.left, key);
        else if (key > n.key) n.right = insert(n.right, key);
        return n;
    }

boolean contains(int key) {
        // TODO: iterative search
        return false;
    }

boolean delete(int key) {
        // TODO: return false if absent; otherwise root = delete(root, key)
        return false;
    }

private Node delete(Node n, int key) {
        // TODO: the three cases, using the in-order successor
        return n;
    }

// TODO: height(), preOrder(), inOrder()
}

public class BSTDelete {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        IntBST tree = new IntBST();
        int n = in.nextInt();
        for (int i = 0; i < n; i++) tree.insert(in.nextInt());
        int m = in.nextInt();
        // TODO: process the m deletions, then print the three final lines
    }
}

← D12.1 Build a BST and print its traversals D13.1 Build an AVL Tree →