logo Practice-It logo

Main Page → Problems → Solve a Problem

BJP3 Exercise 17.20: makePerfect

Related Links:
Author: Marty Stepp (on 2013/04/01)

Write a method makePerfect that could be added to the IntTree class. The method should add nodes until the binary tree is a "perfect" tree. A perfect binary tree is one where all leaves are at the same level. Another way of thinking of it is that you are adding dummy nodes to the tree until every path from the root to a leaf is the same length. A perfect tree's shape is exactly triangular and every branch node has exactly two children. Each node you add to the tree should store the value 0.

The following table shows the results of a call of your method on a particular IntTree variable named tree: 

IntTree tree = new IntTree();
...
tree.makePerfect();
before call after call> 
                 +----+
                 | 67 |
                 +----+
              /          \
           /                \
      +----+                +----+
      | 80 |                | 52 |
      +----+                +----+
     /      \              /
    /        \            /
+----+     +----+      +----+
| 16 |     | 21 |      | 99 |
+----+     +----+      +----+
            /  \           \
           /    \           \
       +----+  +----+      +----+
       | 45 |  | 33 |      | 67 |
       +----+  +----+      +----+

                        +----+
                        | 67 |
                        +----+
                    /             \
                /                     \
           +----+                     +----+
           | 80 |                     | 52 |
           +----+                     +----+
         /        \                 /        \
       /            \             /            \
   +----+         +----+       +----+        +----+
   | 16 |         | 21 |       | 99 |        |  0 |
   +----+         +----+       +----+        +----+
   /    \         /    \       /    \        /     \
  /      \       /      \     /      \      /       \
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+
|  0 | |  0 | | 45 | | 33 | |  0 | | 67 | |  0 | |  0 |
+----+ +----+ +----+ +----+ +----+ +----+ +----+ +----+

For this problem, you may assume the existence of the following helper method, which you are allowed to call at most once during an entire call to your method: 

public int height() { ... }   // returns height of tree from root to lowest leaf

For example, calling height on the tree above would return 4 because it is 4 levels tall.

You may define private helper methods, but aside from height you may not call any other methods of the class nor create any data structures. Your solution should be recursive and utilize the x = change(x) pattern discussed in the Building Java Programs textbook.

Assume that you are adding this method to the IntTree class as defined below: 

public class IntTree {
    private IntTreeNode overallRoot;
    ...
}
Type your solution here:


This is a partial class problem. Submit code that will become part of an existing Java class as described. You do not need to write the complete class, just the portion 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.