[Solved]Java Need Add Functionality Binary Search Tree Improve Search Waldo Public Class Touristli Q37102543

In JAVA, we need to add functionality to the binary search treeto improve the search for Waldo. :

public class touristList {

   class Node {

       public String touristName;
       public int passportNumber;
       public StringdestinationCity;
       private Node next;

       private Node(String t, int p,String c, Node n)
       {
           super();
           touristName =t;
           passportNumber =p;
           destinationCity= c;
           next =null;
       }

       @Override
       public String toString()
       {
           return “Node[Tourist name=” + touristName + “, Passport number=” +passportNumber + “, Destination city=” + destinationCity+”]”;
       }
   }
   Node head= null;
   int size;

   // Add new tourist to the beginning of thelist
   public void addFirst(String t, int p, String c)
   {
       Node tourist = new Node(t, p, c,null);
  
       tourist.next = head;
       head = tourist;
       size++;
   }
   // Finds the node tourist’s name and returns thedestination city
   public String findNode(String t)
   {
       String looking = “”;
       Node lucky = head;
      
       while (lucky != null) {
      
           if(lucky.touristName.equals(t))
             
              return lucky.destinationCity;
           lucky =lucky.next;
       }
       return looking;
   }
      
   // return size of the tourist list
   public int size() {
       return size;
   }
}

New tasks: Now we need a method to return thedestination of the first tourist (alphabetically first by name), amethod to return the destination of the last tourist(alphabetically last by name) and a method to load the BST from asorted array of tourist nodes. Note: you do not need to sort thearray, just load the array in alphabetical sorted order by touristname in main.

Requirements:

Binary Search Tree Class

Start with a generic BST class and move the nested node class soit is an independent class (not nested). Then, add the followingmethods. The first name listed for each method is the wrappermethod name, followed by the recursive method name when recursionis required:

FindMin / FindMinNode [ Recursive ]

Finding the minimum key in a binary search tree simply involvesrecursing down the left branches until a leaf node is reached andreturning the value in that node.

FindMax / FindMaxNode [ Recursive ]

Finding the maximum key in a binary search tree simply involvesrecursing down the right branches until a leaf node is reached andreturning the value in that node.

Load / LoadArray [ Iterative or Recursive]

Load the binary search tree from a sorted array of nodes. Thismethod should accept a sorted array of nodes as a parameter. Note:You do not need to sort the array. Just load the array in sortedorder before passing it as an argument.

This method should load the sorted array into the tree to createa balanced binary search tree so that all levels are at minimumdepth. For example, with an array of 15 values, your method shouldcreate a full and complete binary tree with a depth of 3 because abalanced tree of 15 nodes will include levels 0-3. The image belowshows where indexes 0-14 would be loaded into the BST. Note thatthe numbers in the graphic represent the original array indexes,not the node values.

Hints:

The pseudo code for loading the first node into the BST mightlook something like this:

• calculate the middle of the array (mid)
• insert the mid node into the BST.

Note: This will insert the first node, but inserting all nodesinvolves the same basic steps as long as you calculate the middleof the array correctly for the left and right subtrees. Considerthe binary search on a sorted array for help with calculating themiddle index:

Binary Search on a Sorted Array: Iterative vs. Recursive

Recursive Binary Search on a Sorted Array (Links to an externalsite.)Links to an external site.

Main Class

The main class will contain the main method for testing. Itshould include a minimum of these tasks:

• Create an array of tourist nodes.
• Insert nodes in sorted order into the array including a nodefor Waldo. The key will be the tourist’s name and the value will bethe tourist’s destination.
• Create an object of the Binary Search Tree class that includesthe methods described above and call these methods:
  • Load: pass the array of tourists
  • FindMin: display the return value for the first tourist
  • FindMax: display the return value for the last tourist
  • getValue: Pass the name “Waldo” and display the returnvalue.

Note: Once you load your binary search tree, it must be balancedfor the number of nodes. For example, if your array is size 3, themaximum depth should be 1 because the root is at depth 0, and itschildren are at depth 1. Similarly, if your array is size 7, themax depth should be 2 and for an array of size 15, the maximumdepth should be 3 (see the above graphic). Consider writing amethod or researching a method online that returns the max depth ofa BST for testing purposes (optional).

Depth: 0 7 11 Depth1 3 9 13 4 6 10 14! 12 Show transcribed image text Depth: 0 7 11 Depth1 3 9 13 4 6 10 14! 12

Expert Answer

---

Answer to In JAVA, we need to add functionality to the binary search tree to improve the search for Waldo. : public class touristL… . . .