Let B be the set of all binary trees. Let 2 B denote the empty tree with no vert

Question

Let B be the set of all binary trees. Let 2 B denote the empty tree with

no vertices or edges. For any non-empty tree we write T = hL; Ri 2 B where

L; R 2 B represent the left and right subtrees of the tree T respectively.

Now consider the following recursively dened function:

Prove using induction that for all T 2 B, f(T) is the number of leaves

in T.

Let B be the set of all binary trees. Let 2 B denote the empty tree with no vertices or edges. For any non-empty tree we write T = hL; Ri 2 B where L; R 2 B represent the left and right subtrees of the tree T respectively. Now consider the following recursively dened function: f( lambda ) = 0

Explanation / Answer

Let BT be the set of binary trees over A, and consider the function

f : BT ? N de?ned recursively as follows.

f (hi) = 0

f (hL,x, Ri) =

1 , if L = R = hi

f (L) + f (R) , otherwise

Prove: For all T ? BT, f (T) is the number of leaves in T.

By structural induction on T.

Basis: f (hi) = 0, which is the number of leaves in hi.

Induction: L, R ? BT, x ? A.

IH: f (L) is the number of leaves in L

and f (R) is the number of leaves in R.

NTS: f (hL,x, Ri) is the number of leaves in hL,x, Ri.

Subcase 1: L = R = hi

In this subcase, the number of leaves in hL,x, Ri is 1 = f (hL,x, Ri).

Subcase 2: Otherwise.

Here, the number of leaves in hL,x, Ri is the number of leaves in L plus the

number of leaves in R, which, by IH, is exactly f (L) + f (R) = f (hL,x, Ri).

http://www.d.umn.edu/~ddunham/cs3512s11/notes/l11.pdf

Link for the solution is given above. :)

Be happy :)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.