Application lab in Binary Search Trees

Mission

Delete a key using leaf, one-child, or successor replacement.

Learning outcome: Apply structural deletion cases

Correctness contract

Invariant: Each left-subtree key is smaller and each right-subtree key is larger than its root.

Required technique: Handle leaf, one-child, and two-child deletion explicitly, using the inorder successor for two children.

Complexity target: time O(height); space O(height).

Input and output

Input: n, then n distinct BST keys in insertion order, then one target key. Whitespace may be spaces or line breaks.

Output: Print the requested sequence on one line with single spaces and no trailing space. Return it as a String; Main.java prints it without adding other text.

Assumptions:

• Inserted BST keys are distinct.
• All values fit in signed 32-bit integers.

Before you code

1. Restate the input and output contract, then predict the visible example without running code.
2. Implement the core state transition: Handle leaf, one-child, and two-child deletion explicitly, using the inorder successor for two children.
3. Trace the smallest boundary case, verify exact formatting, and justify the authored time and auxiliary-space bounds.

Implement Practice.solve(Scanner sc). Keep every provided filename and public class name unchanged.

Sample input

5 8 4 12 2 6 2

Sample output

4 6 8 12

Why the sample works: Visible walkthrough for the ordinary non-trivial path. The matching node is reconnected according to its child count; a two-child node uses its inorder successor. Input `5 8 4 12 2 6 2` therefore produces `4 6 8 12`.

Progressive hints

Try the trace and first milestone before opening a hint. Open them in order.

Hint 1 — Contract: identify what each parsed variable represents and write the invariant beside the loop or recursive method.

Hint 2 — Next step: The two-child case becomes a simpler deletion after copying the minimum key from the right subtree.

Hint 3 — Verification: compare the structure state before and after one operation, then test the smallest valid input and a duplicate or unreachable case when allowed.