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.
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.
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
.
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.