A full ternary tree is a rooted tree where each vertex has either 0 or 3 childre

Question

A full ternary tree is a rooted tree where each vertex has either 0 or 3 children. A full ternary tree can be generated using the following recursive definition: Basis step: A single vertex r is a full ternary tree. Recursive step: If T1, T2 and T3 are full, disjoint ternary trees, then there is a full ternary tree consisting of a root node r, with edges connecting to the roots of T1, T2, and T3.

(a) Give a recursive definition of the height H(T) of the full ternary tree.

(b) Give a recursive definition of the number of vertices N(T) in the full ternary tree.

(c) Prove by structural induction that N(T) 3^(H(T)+1) 1 for all full ternary trees.

Explanation / Answer

(a)

        The height of a full ternary tree, written h(T), is defined recursively as follows.

        h(T) = 0

        h(T1 T2 T3) = 1 + max( h(T1); h(T2); h(T3) )

(b)

     The number of nodes in a full ternary tree, written n(T), is dened recursively as follows.

      n(T) = 1

      n(T1 T2 T3) = 1 + n(T1) + n(T2) + n(T3)

(c)

     we have to prove N(T) 3^(H(T)+1) 1 using structural induction

     Here we have to check for 2 steps

    1) Basic Step ( H(T)=0 and H(T)=1 )

    2) Induction Step (for all k = 0,1,........,H(T) for some H(T)>=1)

1)

      If H(T)=0 then we will have only 1 node

      now N(T) 3^(H(T)+1) 1 is

             N(T) 3^(0+1) 1

             N(T) 3-1

             N(T) 2    (Here 1 2 is true)

   If H(T)=1 then we will have only 4 nodes

      now N(T) 3^(H(T)+1) 1 is

             N(T) 3^(1+1) 1

             N(T) 9-1

             N(T) 8    (Here 4 8 is true)

Hence base step is proved.

2)

     from N(T) 3^(H(T)+1) 1

            put H(T) = H(T) + 1

            N(T) 3^(H(T)+1+1) 1

            N(T+1) 3^(H(T+1)+1) 1

       when height is increased by one level as it is full ternary tree a new level will be added to the tree.

Hence N(T+1) 3^(H(T+1)+1) 1.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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