Implement a Binary Search Tree with methods for insertion, deletion, and display

Question

Implement a Binary Search Tree with methods for insertion, deletion, and display. Each node in the tree contains a String, and the order among the nodes is defined by the compareTo() method in String class. If the string to be inserted is already in the tree, or the string to be deleted is not in the tree, nothing should happen --- the operation simply stops, and the program should not crash. When the node to be deleted has two children, replace it using its inorder successor. After each insertion or deletion, display the current tree. The tree is shown sideway, with a parent on left, children on right, and left child above right child. For example, in the following display, P is the parent, L is the left child, and R is the right child.

..............L

P

..............R

Do not display "null" for empty subtree. The program should work by repeating a working cycle, and in each iteration the user can choose from insert(string), delete(string), or exit().

Explanation / Answer

// BinarySearchTree class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // boolean contains( x ) --> Return true if x is present // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // void printTree( ) --> Print tree in sorted order // ******************ERRORS******************************** // Throws UnderflowException as appropriate /** * Implements an unbalanced binary search tree. * Note that all "matching" is based on the compareTo method. * */ public class BinarySearchTree

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.