## BJP4 Exercise 17.20: makePerfect

Author: Marty Stepp (on 2016/09/08)

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;
...
}
```