4 Recursive Definitions and Structural Induction Consider the following recursiv
ID: 3880851 • Letter: 4
Question
4 Recursive Definitions and Structural Induction Consider the following recursive definition of binary trees: Base Case: A single vertex is a binary tree, and we call this vertex a root of that tree. Recursive Case: If v is a single vertex and To and T are two binary trees with roots respectively vo and vi, then the following is a binary tree with root v: A vertex v with a left outgoing edge from v to the root of To and a right outgoing edge from v to the root of Ti Call a vertex in a tree a leaf if it has no outgoing edges, and call it an internal node otherwise. 1. Give a recursive definition of function L s.t. L(T) is a number of leaves in binary tree T 2. Give a recursive definition of function I s.t. I(T) is a number of intenal nodes in T. 3. Prove using structural induction that L(T) = 1(T) + 1.Explanation / Answer
Answer:
Ans 1)
Function L(T) //count number of leaves
if T is NULL
return 0
end if
if left of T is NULL and right of T is NULL
return 1
else
return L(left of T) + L(right of T)
end if
end function
Ans 2)
function I(T) //count number of internal nodes
count = 0
if left of T not NULL OR right of T not NULL
count = 1
if left of T not NULL
count = count + I(left of T)
end if
if right of T not NULL
count = count + I(right of T)
end if
end if
return count
end function
Ans 3)
Proof through structural induction
Say no. of leaves are 0 i.e I(T) = 0
So then L(T) = 1
This is obvious.
Let there are m leaves in a binary tree T.
Hence L(Tm) = m+1
for m+1 leaves:
L(Tm+1) = m+2 = m+1+1 = L(Tm) + 1
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.