Some thoughts after the midterm

First of all, I have to say reading the questions carefully is more important than understanding the question. e.g. Q2 on the midterm, the question was asking number of leaves instead of number of total nodes in the tree, which makes the question lot easier by only asking the lowest level of the tree. From the observation, the worst-case is when we have a full binary tree, where it's lowest level always has 2^(n-1) leaves.

Second, any non-full binary trees will be smaller than full binary trees, therefore we can prove in both cases, P(n) is true!