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:

Explanation / Answer

1) Case 1 only 1 node

   then tree is only that node i.e 1

Case 2

if height of tree is 1

then tree = 1+left(tree) + right(tree)

case N

if height of tree is N-1

then tree = 1+lefttree(N-1) +righttree(N-1)

therefore Since at all levels this condition holds true

SO as a whole we say that tree originated from root node and can be completely represented as 1+lefttree+right tree;

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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