C Programming Question:

Write a C - program to implement the following three operations:

a) Breadth-first search using Adjacency List

b) Breadth-first search using Adjacency Matrix

c) Check whether a given graph is Bipartite using Breadth-first search (adjacency list).​​​​​​

Please take your time, but do submit the correct and full code. Thank you very much.

Circle Class (This is in JAVA)

/**
 * Defines a basic shape with just area
 *
 * @author Jo Belle
 * @version 0.2 (10/05/2020)
 */
public class Shape{
    private double area;

    public Shape(){ area = 0.0; }
    public Shape( double a ){ this.area = a; }
    public void setArea( double a ){ area = a; }
    public double getArea(){ return area; }
    public String toString(){
        return "Shape:\n\tarea: " + area;
    }
}

/**
 * Create a simple Circle object
 *
 * @author Jo Belle
 * @version 0.2 (10/12/2020)
 */
public class ShapeDriver{
    public static void main( String[] args ){
        Circle cir = new Circle( );
        cir.setRadius( 5.0 );
        System.out.println( cir.toString() );
    }
}

Given the code above, write a Circle class (and save it in a file named Circle.java) that inherits from the Shape class. Include in your Circle class, a single private field double radius. Also include a method void setRadius(double r) (which also sets area) and a method double getRadius() (which also returns the current radius). Change the accessibility modifier for area in the Shape class to be more appropriate for a base class. Make sure that ShapeDriver's main() method executes and produces the following output:

Shape:
        area: 78.53981633974483
        radius: 5.0

Submit both your Circle.java and your Shape.java files.

Develop the following class: Class Name: ImprovedArrayBasedStack Access Modifier: public Implements: ImprovedStackInterface Instance variables Name: top Access modifier: private Data type: int Name: stack Access modifier: private Data type: T[] (an array of parameterized type) Constructors Name: ImprovedArrayBasedStack Access modifier: public Parameters: none (default constructor) Task: sets the value of top to -1 sets the stack to refer to an array of Objects with 100 elements which are type cast to T[] Name: ImprovedArrayBasedStack Access modifier: public Parameters: size (data type int) Task: sets the value of top to -1 sets the stack to refer to an array of Objects with the number of elements equal to the size parameter which are type cast to T[] Methods Name: push Access modifier: public Parameters: item (data type T, parameterized type) Return type: void Throws: StackFullException Task: if the value of top is less than the length of the stack minus 1 then increase the value of top by 1 and place the item at the top of the stack, otherwise throw a StackFullException with the message "Not enough room for one item" Name: push Access modifier: public Parameters: item1 (data type T, parameterized type), item2 (data type T, parameterized type) Return type: void Throws: StackFullException Task: if the value of top is less than the length of the stack minus 2, then increase the value of top by 1 and place item1 at the top of the stack, then increase the value of top by 1 and place item2 at the top of the stack, otherwise throw a StackFullException with the message "Not enough room for two items" Name: pop Access modifier: public Parameters: none Return type: void Throws: StackEmptyException Task: if the value of top is greater than -1 then remove the item at the top of the stack by replacing it with null and decrease the value of top by 1, otherwise throw a StackEmptyException with the message "No item to remove" Name: doublePop Access modifier: public Parameters: none Return type: void Throws: StackEmptyException Task: if the value of top is greater than 0, then remove the item at the top of the stack by replacing it with null and decrease the value of top by 1, then remove the item at the top of the stack by replacing it with null and decrease the value of top by 1, otherwise throw a StackEmptyException with the message "There are less than two items in the stack" Name: top Access modifier: public Parameters: none Return type: T (parameterized type) Throws: StackEmptyException Task: if the value of top is greater than -1 then return the item at the top of the stack, otherwise throw a StackEmptyException with the message "Top attempted on an empty stack"

Suppose you define the class myGrid in Java. Suppose further that my Image[][] is a variable defined to be a 2D array with 100 rows and 100 columns of type myGrid, and that the myGrid class has two methods: setX()and setY(). Write the Java code snippet to instantiate every cell of myImage[][]with myGrid objects, and use the setX()and setY()methods to store the row and the column location of each myGrid object in the array.

9. For this question you need to write some methods and class headers.

   1. (a) Assume that you have written a Rectangle class with instance variables length and width. You have already written all set and get methods and area and perimeter methods. Write an equals() method that takes Object o as a parameter. The method should return true when the Object o is a rectangle with the same length and width.

      Answer:

   2. (b) A class named Fruit implements an interface called Edible. The interface has a single method called howToEat(). A class called Orange extends Fruit and implements Edi- ble. Write the class header for the Orange class and override the howToEat() method of the Fruit class. The method should print a brief message to the screen about how to eat an orange. Do not write any other methods or constructors.

      Answer:

Choose a pivot using the median of 3 technique and show the result after 1 pass of quicksort (stop just before choosing a 2nd pivot) for the list [ 85, 40,60, 30, 55, 63, 70, 75 ,25]

Write the algorithm in pseudocode for scan-converting (filling in the interior) of an axis-aligned right triangle (the base is aligned with the x-axis and the orthogonal leg is aligned with the y-axis).

Create a Java method that takes a String as input value and returns the number of vowels contained in that string.

(JAVA)
For your homework, I want you to create the order of your mini-programs based on how it is listed in this assignment description (i.e., Program 1 should be the first program implemented, Program 2 should be the second program, etc.). All your mini-programs are housed inside one main method. The name of your class for this homework should be called Homework3. You will be submitting that single Java file to this submission box. There are a total of two mini-programs you have to implement, and each program is worth 40 points for functioning code and correct outputs. Altogether, the programs are 80 points in total; the remaining 20 points reflect your programming style and documentation.

Program 1 - Palindrome

A palindrome is a sequence of characters that reads the same backward as forward. For example, each of the following five-digit integers is a palindrome: 12321, 55555, 45554, and 11611. Write an application that reads in a five-digit integer and determines whether it's a palindrome. If the number is not five digits long, display an error message and allow the user to enter a new value.

Sample Input
Enter a number: 11611

Sample Output
11611 is a palindrome.

Sample Input
Enter a number: 55953

Sample Output
55953 is not a palindrome.

Sample Input
Enter a number: 1151
Enter a number: 3920
Enter a number: 12321

Sample Output
12321 is a palindrome.

Sample Input
Enter a number: 116611
Enter a number: 999999
Enter a number: 99989

Sample Output
99989 is not a palindrome.

Program 2 - Printing the Decimal Equivalent of a Binary Number

Write an application that inputs an integer containing only 0s and 1s (i.e., a binary integer) and prints its decimal equivalent. [Hint: Use the remainder and division operators to pick off the binary number's, digits one at a time, from right to left. In the decimal number system, the rightmost digit has a positional value of 1 and the next digit to the left a positional value of 10, then 100, then 1000, and so on. The decimal number 234 can be interpreted as 4 * 1 + 3 * 10 + 2 * 100. In the binary number system, the rightmost digit has a positional value of 1, the next digit to the left a positional value of 2, then 4, then 8, and so on. The decimal equivalent of binary 1101 is 1* 1 + 0 * 2 + 1 * 4 + 1 * 8, 1 + 0 + 4 + 8, or 13]

Sample Input
Enter a binary number: 1101

Sample Output
13 is the decimal equivalent of 1101

Sample Input
Enter a binary number: 1000110

Sample Output
70 is the decimal equivalent of 1000110

Sample Input
Enter a binary number: 11111111

Sample Output
255 is the decimal equivalent of 11111111

Sample Input
Enter a binary number: 1001001110

Sample Output
590 is the decimal equivalent of 1001001110

JAVA

Overview

This program implements a simple, interactive calculator.

Major topics

• writing a program from scratch
• multiple methods
• testing

In this document

• program logic & program structure (class, methods, variables)
• input / output
• assumptions and limitations
• documentation & style
• suggested schedule
• cover letter discussion questions
• grading, submission, and due date
• additional notes
• challenges
• sample output
• test plan

Program Logic

• The program prompts the user to select a type of math problem (addition, subtraction, multiplication, or division), enter the two operands, then calculates and outputs the answer.
• The program runs until the user does not want to do any more problems.
• A final tally of problems is printed at the end.

Program Structure and Data

                                                   Calculator class

• one class named FirstnameLastname_02_CS1Calculator
• methods: use the method descriptions as English comments in the code, laying out each logic step to be written in Java
  • main: calls constructor, printIntro, calculate, print report
  • constructor: initializes counters to zero, instantiates and initializes a Scanner to read from the keyboard
  • printIntro method: explains program to user
  • calculate method: primary method with a loop until the user is done
    • run a while loop until the user doesn't want to do another problem
      • display operation choices
      • get user choice, echo their choice (print it back on the screen)
        • use if-elses for which operation to print
      • get operands (numbers to use in the math problem)
      • calculate and print answer
        • use if-elses to pick which math formula
      • count operation type (addition, etc.)
        • use if-elses to pick which counter to increment
      • ask if the user wants to do another problem
    • calculate total problems done (addition count + subtraction count + …)
  • printReport method
    • outputs total of each problem done and overall total problems (see sample output)
• instance (class level) data
  • a Scanner (needs an import statement)
  • 4 ints to count the number of each problem type (addition, etc.)
  • 1 int to hold total problem count
• local variables: as needed in each method (perhaps none in some methods)

I/O

• interactive only (keyboard & screen), no data files
• input
  • user
    • enters the type of problem (addition, etc.)
    • enters two numbers for each calculation
    • enters the decision whether to do more problems
  • the user may enter either uppercase or lowercase for the continuation answer and the problem type selection
  • reading numbers: all input is String type, so it must be converted to int using a parser method from the Integer class:

firstOperand = scan.nextLine();

firstNumber = Integer.parseInt(firstOperand);

• output (see sample output later in this document)
  • directions to the user about the problem
  • prompts to choose problem type and to enter numbers
  • calculated answer to the math problem
  • summary of problem types completed

Assumptions & Limitations

• integers only (no real numbers)
• input numbers and answers will fit in the range of the int data type
• division is integer division
• binary operations only (two operands)
• addition, subtraction, multiplication, division and exit are the only operations supported
• perfect user: all input will be correct (y or n only; integers only for operands)
• results are not saved
• the user will do at least one problem

Test Plan

• Run the following test data, divided into sessions so that total problem counts can be checked. Restart the program to run each session (set of multiple, related problems). Be sure to check that each result is correct.

• Simple basic problems, all operations
  • test 1: 111 + 222 = 333
  • test 2: 9999 + 8888 = 18887
  • test 3: 83 / 83 = 1
  • test 4: 84 / 83 = 1
  • test 5: 83 / 84 = 0
  • test 6: 0 – 0 = 0
  • test 7: 500000 + 500001 = 10000001
  • totals
    • Addition problems: 3
    • Subtraction problems: 1
    • Multiplication problems: 0
    • Division problems: 3
    • Total problems: 7

Note: no tests for bad data since this program is guaranteed a perfect user (i.e., no bad input).

Further work / challenges For any you do, run additional test cases to check the new functionality.

• Add the modulus (remainder) function as a fifth choice for the user. Include a counter for "mod" problems. The math symbol for mod is % (but it does not do anything related to percentage).
• Experiment with the NumberFormat class to learn how to place commas in results larger than 999 and include that for answers before they are printed.
• Instead of printing "The answer is", print the result in math format:

3 + 12 = 15

• Print totals for each type only if the user did any of that type. For example, if they did not do any subtraction problems, don't print the report line listing zero subtraction problems. Use if statements to control printing or not, by looking at the counter for that problem type.

Discussion Questions (cover letter)

1. Overflow. Find out what happens when you try to add two numbers whose sum exceeds the maximum integer value (just over two billion, one hundred million). Test two billion plus two billion. What result did you get? Explain why overflow happens on a computer.
2. Explain inexact results on integer division such as:

2 / 5 = 0 and 51 / 25 = 2

3. What syntax (Java grammar rules) did you have the most trouble getting right?
4. What semantics (meaning of the code) did you have the most trouble understanding?

This is in JAVA

Bank Accounts 01: Child Classes

Copy the following SimpleBankAccount class and use it as a base class:

/**
 * Simple representation of a bank account
 *
 * @author Jo Belle
 * @version 0.5 (10/12/2020)
 */

import java.text.NumberFormat;

public class SimpleBankAccount{
    // fields (instance variables)
    private double balance;
    private String accountId;

    /**
     * Constructor for objects of class SimpleBankAccount
     */
    public SimpleBankAccount(){
        balance = 0.0;
        accountId = "";
    }

    /**
     * Constructor for objects of class SimpleBankAccount
     */
    public SimpleBankAccount( double bal, String id ){
        balance = bal;
         accountId = id;
    }

    /**
     * Add money to the balance
     *
     * @param  amount the amount to deposit
     * @return void
     */
    public void deposit( double amount ){
        balance += amount;
    }

    /**
     * Remove money from the balance
     *
     * @param  amount the amount to withdraw
     * @return true (success) or false (failure)
     */
    public boolean withdraw( double amount ){
        if( balance - amount >= 0 ){
            balance -= amount;
            return true;
        }else{
            return false;
        }
    }

    /**
     * Get the balance
     *
     * @return the balance
     */
    public double getBalance(){
         return balance;
    }

    /**
     * Set account ID
     *
     * @param the account ID
     */
    public void setAccountId(String id){
         accountId = id;
    }


    /**
     * Get the account ID
     *
     * @return the account ID
     */
    public String getAccountId(){
         return accountId;
    }

    /**
     * Produces a string represenation of the balance
     * @return The balance (with a label)
     */
    public String toString( ){
        // display balance as currency
        String balanceStr = NumberFormat.getCurrencyInstance().format( balance );
        return "Balance for account " + accountId + ": " + balanceStr + "\n";
    }
}

Include at least two classes: CheckingAccount and SavingsAccount. Save your CheckingAccount class in a file named CheckingAccount.java and your SavingsAccount class in a file named SavingsAccount.java. Your CheckingAccount class needs to add a field to track the last processed check number. Also include both a no-argument constructor and a parameterized constructor (that takes a double and a String). Furthermore, include the following method:

public boolean processCheck( int checkNum, double amount );

which returns false if checkNum has the same check number as the last check processed, otherwise it reduces the balance by amount and returns true.
Your SavingsAccount class needs to have a field for the interest rate. Also include both a constructor that just takes the interest rate (as a double) and a parameterized constructor (that takes a double, String and a double). Furthermore, include an applyInterest() method that multiples the current balance by the interest rate, and adds that to the balance.
The following code should work and produce the output below:

/** 
 * Exercises the basic functionality of a Checking and SavingsAccount
 *
 * @author Jo Belle
 * @version 0.3 (10/12/2020)
 */
public class AccountsDriver{
    final public static double INTEREST_RATE = 0.01;  // 1%

    public static void main( String[] args ){
        CheckingAccount checking = new CheckingAccount( 100.0, "checking123" );
        SavingsAccount savings = new SavingsAccount( 1000.0, "savings124", INTEREST_RATE );

        double monthlyExpenses = 756.34;
        int electricBillCheckNum = 2123;
        double electricBill = 60.34;
        int registationCheckNum = 2124;
        double registration = 50.00;
        double dinnerMoney = 55.32;
        double futureCar = 200.0;
        double textbook = 90.0;

        // checking account transactions
        checking.deposit( monthlyExpenses );
        checking.processCheck( electricBillCheckNum, electricBill );
        checking.withdraw( dinnerMoney );
        checking.processCheck( registationCheckNum, registration );
        System.out.print( checking.toString() );
        System.out.println( );

        // savings account transactions
        savings.deposit( futureCar );
        savings.applyInterest( );
        savings.withdraw( textbook );
        System.out.print( savings.toString() );
        System.out.println( );
    }
}

Output:

Checking Account:
Balance for account checking123: $690.68
Last processed check number: 2124

Savings Account:
Balance for account savings124: $1,122.00
APR: 1.0%

Make just the necessary changes to the code in SimpleBankAccount to complete the instructions.
Submit the following files:

• CheckingAccount.java
• SavingsAccount.java
• SimpleBankAccount.java

Can someone please complete the following code(Java). The stuff in comments are the things you need to look at and code that

package mini2;

import static mini2.State.*;

/**

* Utility class containing the key algorithms for moves in the

* a yet-to-be-determined game.

*/

public class PearlUtil

{

private PearlUtil()

{

// disable instantiation

}

/**

   * Replaces all PEARL states with EMPTY state between indices

   * start and end, inclusive.

   * @param states

   * any array of States

   * @param start

   * starting index, inclusive

   * @param end

   * ending index, inclusive

   */

public static void collectPearls(State[] states, int start, int end)

{

// TODO

}

/**

   * Returns the index of the rightmost movable block that is at or

   * to the left of the given index start. Returns -1 if

   * there is no movable block at start or to the left.

   * @param states

   * array of State objects

   * @param start

   * starting index for searching

   * @return

   * index of first movable block encountered when searching towards

   * the left, starting from the given starting index; returns -1 if there

   * is no movable block found

   */

public static int findRightmostMovableBlock(State[] states, int start)

{

// TODO

return 0;

}

/**

   * Creates a state array from a string description, using the character

   * representations defined by State.getValue. (For invalid

   * characters, the corresponding State will be null, as determined by

   * State.getValue.)

   * Spaces in the given string are ignored; that is, the length of the returned

   * array is the number of non-space characters in the given string.

   * @param text

   * given string

   * @return

   * State array constructed from the string

   */

public static State[] createFromString(String text)

{

// TODO

return null;

}

/**

   * Determines whether the given state sequence is valid for the moveBlocks

   * method. A state sequence is valid for moveBlocks if

   *

   *

• its length is at least 2, and

     *

• the first state is EMPTY, OPEN_GATE, or PORTAL, and

     *

• it contains exactly one boundary state, which is the last element

     * of the array

     *

   * Boundary states are defined by the method State.isBoundary, and

   * are defined differently based on whether there is any movable block in the array.

   * @param states

   * any array of States

   * @return

   * true if the array is a valid state sequence, false otherwise

   */

public static boolean isValidForMoveBlocks(State[] states)

{

// TODO

return false;

}

/**

   * Updates the given state sequence to be consistent with shifting the

   * "player" to the right as far as possible. The starting position of the player

   * is always index 0. The state sequence is assumed to be valid

   * for movePlayer, which means that the sequence could have been

   * obtained by applying moveBlocks to a sequence that was valid for

   * moveBlocks. That is, the validity condition is the same as for moveBlocks,

   * except that

   *

   *

• all movable blocks, if any, are as far to the right as possible, and

     *

• the last element may be OPEN_GATE or PORTAL, even if there are

     * no movable blocks

     *

   *

   * The player's new index, returned by the method, will be one of the following:

   *

   *

• if the array contains any movable blocks, the new index is just before the

     * first movable block in the array;

     *

• otherwise, if the very last element of the array is SPIKES_ALL, the new index is

     * the last position in the array;

     *

• otherwise, the new index is the next-to-last position of the array.

     *

   * Note the last state of the array is always treated as a boundary for the

   * player, even if it is OPEN_GATE or PORTAL.

   * All pearls in the sequence are changed to EMPTY and any open gates passed

   * by the player are changed to CLOSED_GATE by this method. (If the player's new index

   * is on an open gate, its state remains OPEN_GATE.)

   * @param states

   * a valid state sequence

   * @return

   * the player's new index

   */

public static int movePlayer(State[] states)

{

// TODO

return 0;

}

/**

   * Updates the given state sequence to be consistent with shifting all movable

   * blocks as far to the right as possible, replacing their previous positions

   * with EMPTY. Adjacent movable blocks

   * with opposite parity are "merged" from the right and removed. The

   * given array is assumed to be valid for moveBlocks in the sense of

   * the method validForMoveBlocks. If a movable block moves over a pearl

   * (whether or not the block is subsequently removed

   * due to merging with an adjacent block) then the pearl is also replaced with EMPTY.

   *

   * Note that merging is logically done from the right.

   * For example, given a cell sequence represented by ".+-+#", the resulting cell sequence

   * would be "...+#", where indices 2 and 3 as move to index 3 and disappear

   * and position 1 is moved to index 3.

   * @param states

   * a valid state sequence

   */

public static void moveBlocks(State[] states)

{

// TODO

}

}

Here's the class where you can check your code

package mini2;

/**
* Possible cell states for a certain puzzle game.
*/
public enum State
{
// WARNING: if we change these, be sure to update the TEXT array too!
EMPTY,
WALL,
PEARL,
OPEN_GATE,
CLOSED_GATE,
MOVABLE_POS,
MOVABLE_NEG,
SPIKES_LEFT,
SPIKES_RIGHT,
SPIKES_DOWN,
SPIKES_UP,
SPIKES_ALL,
PORTAL;
  

public static boolean isMovable(State s)
{
return s == MOVABLE_POS || s == MOVABLE_NEG;
}
  

public static boolean canMerge(State s1, State s2)
{
return s1 == MOVABLE_POS && s2 == MOVABLE_NEG ||
s2 == MOVABLE_POS && s1 == MOVABLE_NEG;
}
  

  
public static boolean isBoundary(State s, boolean containsMovable)
{
if (!containsMovable)
{
return s == CLOSED_GATE ||
s == SPIKES_LEFT ||
s == SPIKES_RIGHT ||
s == SPIKES_DOWN ||
s == SPIKES_UP ||
s == SPIKES_ALL ||
s == WALL;
}
else
{
return s == CLOSED_GATE ||
s == SPIKES_LEFT ||
s == SPIKES_RIGHT ||
s == SPIKES_DOWN ||
s == SPIKES_UP ||
s == SPIKES_ALL ||
s == WALL ||

  
s == OPEN_GATE ||
s == PORTAL;
}
}
  

public static final char[] TEXT = {
'.', // EMPTY,
'#', // WALL,
'@', // PEARL,
'o', // OPEN_GATE,
'x', // CLOSED_GATE,
'+', // MOVABLE_POS,
'-', // MOVABLE_NEG,
'<', // SPIKES_LEFT,
'>', // SPIKES_RIGHT,
'v', // SPIKES_DOWN,
'^', // SPIKES_UP,
'*', // SPIKES_ALL,
'O'// PORTAL;
};
  

public static final char NULL_CHAR = 'n';
  

public static char getChar(State s)
{
if (s == null)
{
return NULL_CHAR;
}
else
{
return TEXT[s.ordinal()];
}
}
  
  
public static State getValue(char c)
{
int i;
for (i = 0; i < TEXT.length; ++i)
{
if (TEXT[i] == c)
{
break;
}
}
if (i < TEXT.length)
{
return State.values()[i];
}
else if (c >= 'A' && c <= 'Z')
{
return State.PORTAL;
}
else return null;
}
  
  
public static String toString(State[] arr)
{
return toString(arr, true);
}
  
  
public static String toString(State[] arr, boolean addSpaces)
{
String text = "";
for (int col = 0; col < arr.length; ++col)
{
State s = arr[col];
char ch = getChar(s);
text += ch;
if (addSpaces && col < arr.length - 1)
{
text += " ";
}
}
return text;
}

  
}

Given two strings X and Y of length n and m respectively, design a dynamic
programming based algorithm to finnd a super-string Z of minimum length such that both
X and Y are subsequence of Z. Note that characters in X and Y do not need to appear
consecutively in Z as long as they appear in the same order in Z as in X or Y . Design an other
algorithm for solving the same problem but with three input strings, W;X; Y , i.e., finding the
minimum length super-string for three strings. Can your algorithm be extended to k input
strings? If so, what would be the running time and space complexities of your algorithm.

I've written three functions to increase the value of a counter in an increment of one, but when I call the functions and then try to print out their values (which should have been updated) I get the values they were originally intialized to which was 0. Below is my code for the 3 functions and where I call them in my main. Can someone please tell me where I'm going wrong?

void addsec(int hr, int min, int sec){

               ++sec;

               if(sec==60){

                              ++min;

                              sec=0;

                              if(min==60){

                                             ++hr;

                                             min=0;

                                             if(hr==24){

                                                            hr=0;

                                             }

                              }

               }

               return;

}

void addmin(int hr, int min){

               ++min;

               if(min==60){

                              ++hr;

                              min=0;

                              if(hr==24){

                                             hr=0;

                              }

               }

return;

}

void addhour(int hr){

               ++hr;

               if(hr==24){

                              hr=0;

               }

return;

}

int main(int argc, char* argv[]){

int sec=0;
int min=0;
int hr=0;

printf("the current value of hour is %d\n", hr);
printf("\n");
printf("the current value of minute is %d\n", min);
printf("\n");
printf("the current value of second is %d\n", sec);
printf("\n");

/*test that add one to hr, min, sec works, then print military and standard time*/
   addsec(hr, min, sec);
   printf("the updated value of second is %d\n", sec);
   printf("\n");
   addmin(hr, min);
   printf("the updated value of minute is %d\n", min);
   printf("\n");
   addhour(hr);
   printf("the updated value of hour is %d\n", hr);
   printf("\n");
...

8.16 Implement code for the BSTRemove operation.

Implement node removal functionality for the BinarySearchTree. The base remove function has already been implemented for you, but you need to fill in the implementation for Case 1, Case 2, and Case 3 of the algorithm as described in the lecture notes.

Note, the pseudo-code in the lecture should work with minimal modifications. However, it would be a good learning exercise to try to implement them from scratch if you have time.

//C++ code

#include <iostream>
#include <random>

class BinarySearchTree {
protected:
// Class to represent a node of a binary tree
class BTNode
{
public:
int data;
BTNode *right;
BTNode *left;
  
BTNode(int d, BTNode *l=nullptr, BTNode *r=nullptr)
{
data = d;
right = r;
left = l;

}
};

BTNode *root;
  
public:
BinarySearchTree()
{
root = nullptr;
}

~BinarySearchTree()
{
// UNCOMMENT ONCE REMOVE WORKS!
//while(root)
// remove(root->data);
}

void insert(int data)
{
BTNode *node = new BTNode(data);

if (root == nullptr)
{
   root = node;
}
else
{   
   BTNode * tmp = root;
   while (tmp != nullptr)
   {  
   if (data < tmp->data)
   {
       // data must be on left side
       if (tmp->left == nullptr)
       {
       tmp->left = node; //
       return;
       }
       else
       tmp = tmp->left;
   }
   else
   {
       // data must be on right side
       if (tmp->right == nullptr)
       {
       tmp->right = node;
       return;      
       }
       else
       tmp = tmp->right;
   }
   }
}

}

bool search(int data) {
BTNode * tmp = root;
while (tmp != nullptr)
{
   if (data == tmp->data)
   return true;
  
   if (data < tmp->data)
   tmp = tmp->left;
   else
   tmp = tmp->right;
}
return false;
}

private:
bool Case1(BTNode *node, BTNode *parent)
{
return false; // not Case 1, try Case 2
}

bool Case2(BTNode *node, BTNode *parent)
{
return false; // not Case 1 or 2, must use Case 3
}

bool Case3(BTNode *node, BTNode *parent)
{
// Case 3 must succeed!
return true;
}
  
public:
void remove(int data) {
BTNode *tmp = root;
BTNode *parent = nullptr;
  
// Find the node in the tree
while (tmp != nullptr)
{
   if (tmp->data == data)
   {
   if (!Case1(tmp,parent))
   if (!Case2(tmp,parent))
       Case3(tmp,parent);

   // delete node once removed  
   //delete tmp; // UNCOMMENT ONCE REMOVE WORKS
   break;
   }          
   else if (data < tmp->data)
   {
   parent = tmp;
   tmp = tmp->left;
   }
   else
   {
   parent = tmp;
   tmp = tmp->right;
   }
}
}

public:
// DO NOT REMOVE OR MODIFY

bool hasRoot() {
return root != nullptr;
}

int getRoot() {
if (hasRoot()) return root->data;
else return -1;
}

bool rootHasRightChild() {
return root->right != nullptr;
}

int getRootRightChild() {
return root->right->data;
}

bool rootHasLeftChild() {
return root->left != nullptr;
}

int getRootLeftChild() {
return root->left->data;
}
public:
friend std::ostream& operator<< (std::ostream& out, BTNode *bt);
friend std::ostream& operator<< (std::ostream& out, BinarySearchTree &bst);
};

std::ostream& operator<< (std::ostream& out, BinarySearchTree::BTNode *bt)
{
if (bt == nullptr)
return out;
  
if (bt->left != nullptr)
out << bt->left;

out << bt->data << " ";

if (bt->right != nullptr)
out << bt->right;

return out;
}

std::ostream& operator<< (std::ostream& out, BinarySearchTree &bst)
{
out << bst.root;
return out;
}

int main()
{
//std::random_device generator;
std::default_random_engine generator;
std::uniform_int_distribution<int> dist(0,1000);

BinarySearchTree *b2 = new BinarySearchTree();
for(int i=0; i<10; i++)
{
b2->insert(dist(generator));
}
for (int i=0; i<5; i++)
b2->insert(i*100);
for(int i=0; i<10; i++)
{
b2->insert(dist(generator));
}

std::cout << *b2 << std::endl;

for (int i=0; i<5; i++)
{
std::cout << "remove " << i*100 << std::endl;
b2->remove(i*100);
}
std::cout << *b2;

delete b2;
  
return 0;
}