G5BADS Informal coursework 3

For tutorials in the week of the 1st-5th December:
  1. Prove by mathematical induction that a perfectly balanced binary tree with k levels contains 2k-1 leaves. Proof:
    Basis of induction (k = 1): a perfectly balanced tree with one level (just the root) has one leaf (one node with no children). 1 = 20 = 21 - 1 so the claim is correct for k = 1.
    Inductive step : if the claim is true for perfectly balanced trees with n levels, it is true for prefectly balanced trees with n+1 levels.
    Assume that in a perfectly balanced tree with n levels there are 2n-1 leaves. A perfectly balanced tree with n+1 levels has twice more leaves (since every node on level n-1, which is a leaf in a tree with n levels, now has two children which are leaves in a tree with n+1 levels). So a pefectly balanced tree with n+1 levels has 2 * 2n-1 = 2n leaves, which is the same as 2(n+1)-1 leaves. If the claim holds for a tree with n levels, it holds for a tree with n+1 levels.
  2. Calculate how many levels a complete binary tree of size x has.
    First of all, recall that perfectly balanced trees contain 1, 3, 7, 15... nodes, the number of nodes being of the form "some power of 2 - 1". The number of levels in a perfectly balanced tree is log2(x+1), where x is the number of nodes. For example, a perfectly balanced tree of size 31 has 5 levels (25 = 32).
    Now if we see a complete binary tree of size x, we need to ask ourselves what would be the smallest perfectly balanced tree which could keep at least that many nodes. For example, if x = 15 we know that the smallest perfectly balanced tree which can keep 15 nodes is a perfectly balanced tree with 4 levels. If x = 17 the nodes would not fit in 4 levels, we need an extra level so need to look at a perfectly balanced tree of size 31.
    So the rule is: if x = 2n - 1 for some integer n, then a complete binary tree of size x contains n levels. Otherwise find the smallest n such that x <= 2n - 1.
    Another way of saying the same thing: take log2(x+1) and round it up to the nearest integer.