Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Problem 2. The recursive data type, binary-2PTG, of binary trees with leaf labels, L, is defined recursively as follows: e Base case: (leaf; l) e
Problem 2. The recursive data type, binary-2PTG, of binary trees with leaf labels, L, is defined recursively as follows: e Base case: (leaf; l) e binary-2PTG, for all labels 1 EL. e Constructor case: If G1; G2 e binary 2PTG, then (bintree; G1; G2) e binary 2PTG. The size, |G], of G e binary-2PTG is defined recursively on this definition by: o Base case: Kleaf; 1)] = 1; VIEL: Constructor case: kbintree; G1; G2) = |G1| + |G2| + 1. For example, the size of the binary-2PTG, G, is 7. RG G win 622 win lose win (a) Write out (using angle brackets and labels bintree, leaf, etc.) the binary-2PTG, G. (b) The value of flatten(G) for G e binary 2PTG is the sequence of labels in L of the leaves of G. For example, for the binary-2PTG, G, flatten(G) = {win; lose; win; win} . Give a recursive definition of flatten. (You may use the operation of concatenation (append) of two sequences.) (c) Prove by structural induction on the definitions of flatten and size that 2 x length(flatten(G)) = [G] +1
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started