Week 7

Assignment 2 is so hard!

Although question 1 is from assignment 1, I still didn't get it this time. The only part of this question that I felt confident about is I managed to show that if a ternary tree has n nodes, there will be (2*n + 1) positions available to add a new node onto the tree. Although I didn't include that into my solution to question 1 since I think it is kind of irrelevant to the problem, I will prove it here.

P(n): if a ternary tree has n nodes, there will be (2*n + 1) positions on the tree available to add a new node.
Claim: \forall n \in N, P(n).
Proof: Base Case: For n = 0, the tree is the empty tree and there is only one position available to add a new node, namely the root. Since 1 = 2*0 + 1, P(0) is true.
Induction Step: assume n \in N and P(n) is true, that is (2*n + 1) positions are available to be added for a ternary tree with n nodes. To add a new node, note that it will take up one old position but itself will open up three new positions for a newer node to be add. Thus, from n to (n + 1), 2 more positions are created. Since 2*n + 1 + 2 = 2*(n + 1) + 1, P(n + 1) is true.
So \forall n \in N, P(n) => P(n + 1).
Thus, \forall n \in N, P(n).

That is everything. Hope the next assignment and the coming test won't be that hard.