CS 240 Spring 2018
Program #4 and Homework #14
Deadline: Friday, April 27th 11:55 PM

Download the BinaryTreeLinked class (just the .h file) from Moodle and implement the following prototyped functions. The functions listed should be in the public section of the class.
You must also implement private recursive functions that actually do the jobs as described.

void printInorder() const;

void countNodesPerLevel(int counts[], int &levels, int arraySize) const;

void countParentTypes(int counts[]) const;

Details:
printInOrder(): Must print the tree’s root value (if there is one) and then print all the tree’s values using an in-order traversal. At each node, you must print the node’s value, then its left child and then its right child. If either or both of the children are nullptr, print “- -“.
For example:
This tree:
Should print like this:

Root: 14
   4  Left child:  --   Right child:    5
   5  Left child:  --   Right child:  --
  14  Left child:    4  Right child:   51
  51  Left child:  --   Right child:   80
  80  Left child:  --   Right child:  --

countNodesPerLevel(): This function must count the number of nodes at each level of the tree, where level one is the root node and the other levels are the nodes that are the same distance from the root. For example, in the tree above, node 14 is on level 1, nodes 4 and 51 are on level 2 and nodes 5 and 80 are on level 3. The array “counts[]” must store the number of nodes at each level, where level 1 is stored at index 0, level 2 at index 1 and so on. So each index (i) stores the number of nodes at level (i + 1). Parameter “levels” should be set to how many levels are in the tree and “arraySize” is how many integers are actually in array “counts”. You must make sure to crash the program if the number of levels ever exceeds “arraySize”.
For example: if this function was called on the tree above, the results would be:
counts[0] = 1
counts[1] = 2
counts[2] = 2
levels = 3

countParentTypes(): This function must count the number of nodes in the tree based on how many children the nodes have. counts[0] must store how many nodes have 0 children, counts[1] must store how many have 1 child and counts[2] must store how many nodes have 2 children.
For example: if this function was called on the tree above, the result would be:
counts[0] = 2
counts[1] = 2
counts[2] = 1

What to turn in:
The BinaryTreeLinked.h with these functions implemented.