Two C# assignment

1. Refer to program p4-1-BinarySearchTree.cs

a. Write code to build a Binary Search Tree with the following nodes: 55, 29, 80, 22, 41, 72, 35, 78, 44, 90, 18, 88, 25, 60. Print screen shot of the run.

b. Add one operation in your program that finds the height of BST. Find the height of the BST you build in a) by calling this method in the Main method

c. Draw the tree (on paper, preferably using MS-Word).

d. Draw the tree after deleting node 90

e. Draw the tree after deleting node 80 (from the original tree, not from after d))

f. Draw the tree after deleting node 55 (from the original tree, not from after d) and e))

g. Draw the tree after inserting a node whose key is 43 to the original BST.

2. In a BST with n nodes, how many comparisons are needed for searching, insertion, and deletion in worst case, respectively? How many comparisons are needed for these operation in average case, respectively?

3. Write the program for BST of Employee records (Employee empID is used as key). The program must contain the following operations:

· Search a node (given an employee’s empID ), and print the record when it is found.

· Insert a node (given a new employee record)

· Delete a node (given an employee’s empID )

· Print out of all employee records in the BST in in-order traversal.

Also, write a Main method to test your program as follows:

· Create an empty BST.

· Insert 10 Employee records one by one into the BST in the following order:

and print the BST in in-order to confirm 10 records are inserted correctly.

· Search an employee record (given an employee’s empID ), and print the employee record if the empID is found.

· Delete an employee record (given an employee’s empID ), and print the BST in in-order to confirm that the record is deleted.

The Employee class is given as follow:

class Employee

{

public string name;

public int empID;

public double salary;

public void Input()

{

Console.Write("Name: ");

name = Console.ReadLine();

Console.Write("ID: ");

empID = int.Parse(Console.ReadLine());

Console.Write("Salary: ");

salary = double.Parse(Console.ReadLine());

}

public Output()

{

Console.WriteLine("[{0}|{1}|{2:C}]", name, empID, salary);

}

}