What will be on the exam

The second midterm exam will cover recursion and binary trees. I will ask two kinds of questions. The first kind of question will ask you construct a recursive function to solve a problem involving a binary tree. The second kind of question will ask you to demonstrate your understanding of some operation in a tree data structure.

Sample recursion questions

Here are some questions that are typical of the recursion problems I might ask. In all of the questions below you may assume that you are dealing with a binary tree composed of nodes of the following type:

class node {
  public:
    int data; // nodes contain int data
    node *left,*right; // left child and right child pointers
    
    node(int el) : data(el),left(nullptr),right(nullptr){}
};

1. Binary search trees can sometimes contain duplicate elements. Construct a recursive function

bool has_duplicates(node *root)

that returns true if the subtree whose root is root contains a duplicate value somewhere in it and false if it does not. In writing this function you may find it useful to construct and use one or more additional functions.

Solution

2. Construct a recursive function

bool missing(node *root,int low,int high)

that returns true if the binary search tree whose root is root contains no data items whose value is greater than or equal to low and less than or equal to high.

Solution

Data structure questions

In the second half of the exam all the questions will follow the same format: I will show you a picture of a data structure and will ask you to draw a picture of what the data structure looks like after we perform some operation on it.

Here is an example. The picture below shows a maximum priority heap. Draw a picture of what the heap looks like after we remove the largest element.

This a list of algorithms you will need to know for this portion of the exam.