Binary Search Trees

Add a displayBothChildren method to the BST class that does not take any arguments and produces output that matches the examples below.
Write Java code in a new driver class named BSTPracticeExercises.java that does the following:

1. Inserts the following values into a new BST:

   {"Binary Search", "AVL", "Two-Three", "Two-Three-Four", "Red-Black", "Splay"}

   and calls displayBothChildren on that BST.

   Binary Search
   + Left  AVL
   + Right Two-Three
           + Left  Red-Black
           |       + Left  (empty)
           |       + Right Splay
           + Right Two-Three-Four

2. Inserts the following values into a new BST:

   {"Splay", "Binary Search", "Red-Black", "AVL", "Two-Three", "Two-Three-Four"}

   and calls displayBothChildren on that BST. Then, adds

   "Two-Three"

   and calls displayBothChildren again. Notice where the repeated value is stored.

   Splay
   + Left  Binary Search
   |       + Left  AVL
   |       + Right Red-Black
   + Right Two-Three
           + Left  (empty)
           + Right Two-Three-Four
   
   Splay
   + Left  Binary Search
   |       + Left  AVL
   |       + Right Red-Black
   + Right Two-Three
           + Left  Two-Three
           + Right Two-Three-Four

3. Inserts the following values into a new BST:

   {"AVL", "Binary Search", "Red-Black", "Splay", "Two-Three", "Two-Three-Four"}

   and calls displayBothChildren on that BST. Notice what the shape of the BST looks like (without the empty subtrees).

   AVL
   + Left  (empty)
   + Right Binary Search
           + Left  (empty)
           + Right Red-Black
                   + Left  (empty)
                   + Right Splay
                           + Left  (empty)
                           + Right Two-Three
                                   + Left  (empty)
                                   + Right Two-Three-Four

The last test case inserts 200 Baby Names and produces the following output which can be found HERE. For this test, the driver code is already in codePost: It inserts all 200 baby names (#1 girl, #1 boy, #2 girl, #2 boy, #3 girl, ...) into a BST object and then calls the displayBothChildren method on that object.

Consider how the the output compares with pre-order, in-order and post-order traversal.

You will also need the following files to compile BST.java on your machine (but you do not need to upload them):

• BSTNode.java
• BinNode.java