Design a recursive divideandconquer algorithm for counting t

Design a recursive, divide-and-conquer algorithm for counting the number of leaves in a binary tree with N nodes. Write the pseudo code, then set up the recurrence relation for your algorithm, solving for efficiency using the master theorem.

Solution

Algorithm:NumberLeaves()

Input:A binary tree T

Output:Count of leaves in T

if T==0 return 0;

else if(T->left==0 and T->right==0) //It checks whether T is Leaf or not

return 1;

=============================================================================

Complexity function T(n) can be defined as:

T(n) = T(k) + T(n – k – 1) + c

Where k is the number of nodes on one side of root and n-k-1 on the other side.

Then compare with Master\'s Theorem

T(n)=aT(n/b)+n^c then T(n)=O(n^{logb a})

Apply Master Theorem,

a=2,b=2,c=0

hence,T(n)=O(n^{logb a})

=O(n)

==================================================

Comment about the work