Source code online books for professionals by professionals

Figure 4-6.  Balance factors for a binary tree. The balance factors are defined only for internal nodes (highlighted) but 
could trivially be set to zero for leaves
14
In general, you should, of course, be careful about making unwarranted assumptions. In the words of Alec Mackenzie (as quoted 
by Brian Tracy), “Errant assumptions lie at the root of every failure.” Or, as most people would put it, “Assumption is the mother of 
all f@#k-ups.” Assumptions in induction are proven, though, step by step, from the base case.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
86
Calculating balance factors isn’t a very challenging algorithm design problem, but it does illustrate a point. 
Consider the obvious (divide-and-conquer) reduction. To find the balance factor for the root, solve the problem 
recursively for each subtree and then extend/combine the partial solutions to a complete solution. Easy peasy.  
Except ... it won’t work. The inductive assumption that we can solve smaller subproblems won’t help us here because 
the solution (that is, the balance factor) for our subproblems doesn’t contain enough information to make the 
inductive step! The balance factor isn’t defined in terms of its children’s balance factors—it’s defined in terms of their 
heights. We can easily solve this by just strengthening our assumption. We assume that we can find the balance factors 
and the heights of any tree with k < n nodes. We can now use the heights in the inductive step, finding both the balance 
factor (left height minus right height) and the height (max of left and right height, plus one) for size n in our inductive 
step. Problem solved! Exercise 4-20 asks you to work out the details here.
Note
 
■
  recursive algorithms over trees are intimately linked with depth-first search, discussed in Chapter 5.
Thinking formally about strengthening the inductive hypothesis can sometimes be a bit confusing. Instead, you 
can just think about what extra information you need to “piggyback” on your inductive step in order to build a larger 
solution. For example, when working with topological sorting earlier, it was clear that piggybacking (and maintaining) 
the in-degrees while we were stepping through the partial solutions made it possible to perform the inductive step 
more efficiently.
For more examples of strengthening induction hypotheses, see the closest point problem in Chapter 6 and the 
interval containment problem in Exercise 4-21.