CodeStepByStep

Write a function named makeFull that accepts a reference to a pointer to the root of a binary tree of integers. 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 node pointer called root points to the root of a tree that stores the elements below, then the call of makeFull(root); 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.

   12
  /
29

   -1
  /  \
29    12

Your function should perform this operation at every level of the tree. For example, if a pointer root2 instead points to a tree that stores the elements below at left, then the call of makeFull(root2); 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.

           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. You may define private helper functions. Your solution should be at worst O(N) where N is the number of elements in the tree. Do not create any data structures (arrays, vectors, sets, maps, etc.). Your solution must be recursive.

Assume that you are using the BinaryTreeNode structure as defined below:

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};