Description
Objective: Check the provided starter code to make sure you have the correct prototypes.
Feel free to modify prototypes if something else is more useful. You will notice in the starter
code I have public helper functions which make it possible to call a routine without knowing
the root, but have recursive “worker” routines that depend on knowing the current node.
These MUST BE your own work. Do not copy from anywhere.
In the comments to each function, provide a big-Oh expression for the complexity of the
functions you write, assuming trees are roughly balanced (depth = log(n) for n nodes).
Use recursion where appropriate, but if something isn’t logically recursive, don’t use
recursion.
Documentation of code and identifying the big-Oh is worth four points. Consult the style guidelines.
Build the trees: tree0, tree1, tree2, tree3, tree4, tree5, tree6 as shown in the starter code.
1. (1 point) Change the insert routine in the code so that each node knows how many nodes are in its
left subtree and how many nodes are in its right subtree. Create a count routine which returns
the number of nodes in the tree.
2. (1 points) Write a function, toString, that returns a string containing: a message and the keys (in
order) of a binary search tree, given the root. This should print the tree prettily. It should show
the parent pointers in parentheses and the number of nodes in the left and right subtrees in
square brackets. For example:
Demonstrate the toString function works by printing tree0.
3. (1 point) Write the function makeEmpty to remove all elements from a tree. Be sure to properly
delete the dynamically allocated nodes. Demonstrate this works by making a clone of tree0,
making it empty, and then showing tree0 hasn’t been affected.
4. (1 points) Write a function, fringe, that returns the count of the leaf nodes of a binary search
tree rooted at root. A leaf is a node with no children.
5. (2 points) Write a function to find the inorder predecessor of a node (given a node in the tree).
You should use the parent link to find the predecessor, but an inorder predecessor is not the
CS 2420 Program 2 Page 2
same thing as a parent. This function can be written in fewer than 10 lines of code – but that’s a
guideline, not a requirement. Note, for each test, we find the predecessor of a given node. This
needs to use a routine that can find a predecessor from a specific node (without having to
traverse the tree from the root). In the tree below, the inorder predecessor of 14 is 11. The
inorder predecessor of 15 is 14. The inorder predecessor of 7 is 6.
6. (2 points) Write the function nodesInLevel that returns the total number of nodes on the
specified level. For this problem, the root is at level zero, the root’s children are at level one,
and for any node, the node’s level is one more than its parent’s level.
7. (3 points) Write the function findKthInOrder. Given an integer k and a binary search tree
with unique values, findKthInOrder returns a pointer to the node that contains the kth
element if the elements are in sorted order – the node with the smallest value is returned
if k = 1, the node with the second smallest is returned if k = 2, and so on.
For example, in the tree shown below (t points to the root), findKthInOrder(t,4) returns a
pointer to the node with value 9, findKthInOrder(t,8) returns a pointer to the node with
value 18, and findKthInOrder(t,12) returns NULL since there are only 9 nodes in the tree.
8. (3 points) By definition, the width of a tree is the number of nodes on the longest path
between two leaves in the tree (not considering the direction of the arcs). The diagram
below shows two trees of width 9. The leaves that form the ends of a longest path are
shaded (note that there is more than one path in each tree of length nine, but no path
longer than nine nodes).
It can be shown that the width of a tree T is the largest of the following quantities:
• The width of T’s left subtree
• The width of T’s right subtree
CS 2420 Program 2 Page 3
• The longest path between leaves that goes through the root of T (this can be
computed from the heights of the subtrees of T)
Here’s code that’s almost a direct translation of the three properties above (assuming
the existence of a standard O(1) max function that returns the larger of two values).
// returns width of tree rooted at t
int width (TreeNode * t)
{
if (t == NULL) return 0;
int leftW = width (t->left);
int rightW = width(t->right);
int rootW = height(t->left) + height(t->right) + 1;
return max(rootW, max(leftW, rightW));
}
However, the function as written does not run in O(n) time because computing height is O(n)
work. Write a version of width that runs in O(n) time. Hint, use a function as described
below.
int widthHeight(TreeNode * t, int & height)
// pre: t is a binary tree
// post: return (via reference param) height = height of t
// return as value of function: width of t
{
}
CS 2420 Program 2 Page 4
9. (2 points) Two binary trees s and t are isomorphic if they have the same shape; the
values stored in the nodes do not affect whether two trees are isomorphic. In the diagram
below, tree a and tree b are isomorphic. Tree c is not isomorphic to the others.
10. (2 points) Two trees s and t are quasi-isomorphic if s can be transformed into t by
swapping left and right children of some of the nodes of s. The values in the nodes are not
important in determining quasi-isomorphism, only the shape is important. For the trees
below tree a and tree b are quasi-isomorphic because if the children of the nodes 10 in
tree a on are swapped, the tree having the same shape as tree b is obtained. All three
trees below are quasiIsomorphic.
Write a function isQuasiIsomorphic that returns true if two trees are quasi-isomorphic.
11. (2 points) Write a function which returns the least common ancestor of a node in a binary
search tree. A least common ancestor is an ancestor of both nodes and is closest to the
nodes. A node is considered to be an ancestor of itself. In the tree below, the least
common ancestor of 82 and 8 is 20. The least common ancestor of 42 and 50 is 50 (even
though 42 doesn’t exist). The least common ancestor of 57 and 40 is 50.
CS 2420 Program 2 Page 5
