The Binary Tree method is Full takes O(n log n) time to execute on full trees, which, as we’ve seen, is not optimal. Careful thought shows that calls to height (an O(n) operation) are made more often...

The Binary Tree method is Full takes O(n log n) time to execute on full trees, which, as we’ve seen, is not optimal. Careful thought shows that calls to height (an O(n) operation) are made more often than is strictly necessary. Write a recursive method info that computes two values—the height of the tree and whether or not the tree is full. (This might be accomplished by having the sign of the height be negative if it is not full. Make sure you do not call this method on empty trees.) If info makes no call to height or is Full, its performance is O(n). Verify this on a computer by counting procedure calls. This process is called strengthening, an optimization technique that often improves performance of recursive algorithms.