CSSE 230
Data Structures and Algorithm Analysis

Small Programming HW 2 - 20 points

To Be Turned In

More tree practice! You will write two methods for Binary Trees. Like the last homework, the trick to these is to add parameters or multiple return values (through your own custom class) to  

1. Full tree constructor. Create a full tree of Integers whose leaves have the given depth, and where every node is labeled with its own depth. It is good experience to know how to build a whole tree by calling a single method. 
2. getSumOfHeights. Find the sum of the heights of every node in the tree. This is an interesting problem if you want to do it efficiently, meaning in O(n) time. Just calling height() on each node will give the correct answer, but it duplicates a lot of work and leads to an O(n log n) algorithm. Could you somehow combine finding the height with finding the sum of the heights in your method? Hint: don't use a field - that has a side effect of modifying each node. Instead, use either multiple return values (which I think is clean) or mutable parameters to do the trick.