## Midterm 2 Review Guide

### Lesson 7 Review

• What is recursion?
• What are the different parts of a recursive method (hint think base case and recursive call)?
• What is the method call stack? Describe how recursion works with the method call stack?
• What is a stack frame?
• What is a stack overflow error?
• What is the difference between iteration and recursion?
• How do you write the following recursive methods: bunnyEars, fibonnacci, powerOfN, factorial?
• How do you write isSorted and printReverse?

### Lesson 8 Review

• What is the Big-O runtime of binary search in the best, worst and average cases
• What is the Big-O runtime of linear search in the best, worst and average cases
• How do you write binary search for an array (recursive)?
• How do you write linear search (not recursive)?
• What is the average case Big-O runtime for all the methods you have written for your labs so far this quarter?

### Trees, Binary Trees, Binary Search Trees

• How is a Tree shaped differently from the linear data structures we have seen so far in this class, and what advantages does this shape offer? (general understanding, not a potential test question)
• What is a Binary Tree?
• How do you determine if a Binary Tree is balanced?
• How do you define a Binary Search Tree ADT?
• How is a BST a recursive structure? (general understanding, not a potential test question)
Given the tree below:

• Label the root, leaves, and interior nodes, and give one example of a child, parent, sibling, descendant, and ancestor relationship.
• What are the height and depth of the nodes 12, 54, and 50?
• Is the above tree a binary tree? Why or why not?
• Is the above tree a BST? Why or why not?
• What is the Big-O run-time of search, insert and delete operations on a BST in best, average and worst case?
• Trace recursive tree traversals inOrder, preOrder, postOrder on the above BST.
• Write the preOrderPrint, inOrderPrint and postOrderPrint helper methods.
• Trace the remove operation on node 76. Then remove 12. Finally, remove 17. For each node you remove, draw your steps and the resulting tree after the element has been removed.
• What are the three cases you need to take into consideration when implementing the BST remove operation?
• How do you write the Java code to handle each of these three operations?
• How do you write the remove method for a BST, both wrapper and helper, based on the pseudocode provided in class?
• What is the purpose of each line of this code?
• How do you write the copy constructor method as an adaptation of preOrderPrint provided in class?
• Write insert and search helper methods for a BST.
• How are these operations similar to the binary search algorithm?
• Draw the BST that results from inserting the following values: 55, 90, 32, 16, 7, 101, 68, 42, 89, 112.

### Hash Tables

• What is a Hash Table?
• What are the advantages of using a Hash Table over other ADTs we have studied?
• Arrays
• Linked Lists (and other linear structures)
• Binary Search Trees
• What is a hashing algorithm?
• How do you write a good hashing algorithm?
• True or False: A method that returns a random number between 0 and the size of the table -1 would be a good hash method.
• Write the hash method defined in class.
• True or False: When implementing a hash method in Java, this method is likely to return a String if the data being stored in the table is String data?
• What is linear probing?
• What is separate chaining?
• How are linear probing and separate chaining different?
• How do you search for an element in a Hash Table?
• Write the search method from Lab 5 - note this method must be efficient O(1) not O(n)
• How do you insert a new element into a Hash Table?
• Write the insert method from Lab 5 - note this method must be efficient O(1) not O(n)
• How do you remove an element from a Hash Table?
• Write the remove method from Lab 5 - note this method must be efficient O(1) not O(n)
• How do you print a Hash Table (2 ways)?
• What is the Big-O runtime of the hash table operations insert, search and remove in the best, worst and average case?
• What is the load factor?
• What is the rule of thumb for selecting a table size, and how does this rule of thumb, along with the concept of the load factor, contribute to creating an efficient Big-O runtime for the the hash table operations? Explain.