## makeFull

Language/Type: C++ binary trees pointers recursion
Author: Marty Stepp (on 2016/06/16)

Write a member function named `makeFull` that could be added to the `BinaryTree` class. A full binary tree is one in which every node has either 0 or 2 children. Your function should produce a full binary tree by replacing each node that has one child with a new node that has the old node as a leaf where there used to be an empty tree. The new node should store a negative value that indicates the level of the tree (-1 for the first level of the tree, -2 for the second level of the tree, and so on).

For example, if a tree called `t` stores the elements below, then the call of `t.makeFull();` should modify the tree to store the elements below at right. Notice that the node storing 12 that used to be at the top of the tree is now a leaf where there used to be an empty tree. In its place at the top of the tree is a new node that stores the value -1 to indicate that it was added at level 1 of the tree.

Your function should also return a count of how many nodes were added to the tree. In this case, it would return `1`.

before call after call
```   12
/
29
```
```   -1
/  \
29    12
```

Your member function should perform this operation at every level of the tree. For example, if a tree `t2` had instead stored the elements below at left, then the call of `t2.makeFull();` should modify the tree to store the elements below at right. Notice that two nodes were added at level 2, and one at level 3. The function would return `3` in this case since 3 nodes were added to the tree.

before call after call
```           12
/    \
28        19
/         /
94        32
/  \         \
65    18        72
```
```           12
/    \
-2        -2
/  \      /  \
94   28    -3   19
/  \       /  \
65    18   32    72
```

Constraints: Do not change the `data` field of any existing nodes of the tree. You will, however, construct new nodes containing negative values to be inserted into the tree and you will change the links of the tree to restructure the tree as described. Do not leak memory. Your solution should be at worst O(N) where N is the number of elements in the tree. You may define private helper functions, but otherwise you may not call any other member functions of the tree class, nor create any data structures (arrays, vectors, sets, maps, etc.). Your solution must be recursive.

Write the member function as it would appear in `BinaryTree.cpp`. You do not need to declare the function header that would appear in `BinaryTree.h`. Assume that you are adding this method to the `BinaryTree` class as defined below:

```class BinaryTree {
private:
BinaryTreeNode* root;   // nullptr for an empty tree
...

public:
};

struct BinaryTreeNode {
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
...
}
```
Type your C++ solution code here:

This is a member function problem. Submit a member function that will become part of an existing C++ class. You do not need to write the complete class, just the member function described in the problem.