CoursHeroTranscribedText 6. In lectures, we considered the set B of binary trees defined recursively by: Base case:

CoursHeroTranscribedText

Transcribed Image Text:

6. In lectures, we considered the set B of binary trees defined recursively by: Base case: the trivial tree t = is in B; Recursive case: if T, T E B then so is the tree T T given by . T T = We can define recursive functions v: B N and e: B N which respectively count the number of vertices and the number of edges of a binary tree. For u we take: Base case: v(t) = 1; Recursive case: v(T T) = u(T) +v(T) + 1. . For e we take: Base case: e(t) = 0; Recursive case: e(T T) = e(T) + e(T) +2. (i) [3 marks]. Evaluate the functions e and u at the binary tree T = (t *t) * (tt). Confirm your answers by drawing the binary tree represented by T; it should have u(T) vertices and e(T) edges. (ii) [4 marks]. Prove by structural induction that, for all binary trees T, we have v(T) = e(T) + 1. 6. In lectures, we considered the set B of binary trees defined recursively by: Base case: the trivial tree t = is in B; Recursive case: if T, T E B then so is the tree T T given by . T T = We can define recursive functions v: B N and e: B N which respectively count the number of vertices and the number of edges of a binary tree. For u we take: Base case: v(t) = 1; Recursive case: v(T T) = u(T) +v(T) + 1. . For e we take: Base case: e(t) = 0; Recursive case: e(T T) = e(T) + e(T) +2. (i) [3 marks]. Evaluate the functions e and u at the binary tree T = (t *t) * (tt). Confirm your answers by drawing the binary tree represented by T; it should have u(T) vertices and e(T) edges. (ii) [4 marks]. Prove by structural induction that, for all binary trees T, we have v(T) = e(T) + 1.