What would be the recurrence relation for an algorithm that

What would be the recurrence relation for an algorithm that counts inner nodes of binary tree? This is the algorithm: count(T): if T is null return 0 else l = count (left subtree of T) r = count (right subtree T) c = l+r if l != null and r != null c+=1 return c

Solution

The Recurrence Relation Will be

f(n)=1+2*f(n-1) where f(0)=0.

Since we are Checking for Left Sub Tree and Right Sub Tree.

If Left is having Children then we will Proceed Left else we will Proceed Right