### Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each

**INSTRUCTIONS TO CANDIDATES**
###### ANSWER ALL QUESTIONS

Design an algorithm for the following operations for a binary tree BT, and show the

worst-case running times for each implementation:

preorderNext(x): return the node visited after node x in a pre-order traversal of BT.

postorderNext(x): return the node visited after node x in a post-order traversal of BT.

inorderNext(x): return the node visited after node x in an in-order traversal of BT.

2. (25 marks) Design a recursive linear-time algorithm that tests whether a binary tree satisfies the

search tree order property at every node.

3. (20 marks) Exercise 8.2. Illustrate what happens when the sequence 1, 5, 2, 4, 3 is added to an empty

ScapegoatTree, and show where the credits described in the proof of Lemma 8.3 go, and how they

are used during this sequence of additions.

4. (20 marks) Implement a commonly used hash table in a program that handles collision using linear

probing. Using (K mod 13) as the hash function, store the following elements in the table: {1, 5, 21,

26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146}.

5. (20 marks) Exercise 6.7. Create a subclass of BinaryTree whose nodes have fields for storing

preorder, post-order, and in-order numbers. Write methods preOrderNumber(),

inOrderNumber(), and postOrderNumbers() that assign these numbers correctly. These

methods should each run in O(n) time.

## Related Questions

##### CSI 1420 Introduction to C Programming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two majorconstructs of the C programming language – Fu

##### The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

##### Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

##### SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1
Project 1
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of

##### Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1
Project 2
Introduction - the SeaPort Project series
For this set of projects for the course, we wish to simulate some of the aspects of a number of