logo CodeStepByStep logo

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;   // NULL for an empty tree
    ...
    
public: 
    your code goes here;
};

struct BinaryTreeNode {
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    ...
}
Type your solution 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.

You must log in before you can solve this problem.


Log In

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.

© Marty Stepp, all rights reserved.