A program takes as input a binary tree (not necessarily balanced) with $n$ nodes and computes for each node, the no. of leaf nodes in the sub-tree rooted at that node. The worst case time complexity of the program is
We just have to do a tree traversal and for leaf nodes return 1 and for other nodes call the function recursively on the left and right nodes and return their sum. The following code would do
int fun (node * x)
if(!x) return 0;
if(x -> left == NULL && x-> right == NULL) return 1;
return fun(x->left) + fun(x->right);
And tree traversal is $\Theta(n)$.
Yes, Answer should be O(n).
Since left/right skewed tree are considered to be the worst case in binary trees.
Consider a left skewed tree/right skewed tree with n nodes.
For left skewed tree, according to the given equation above:
T(n) = T(n-1) + 1
Solving this, we get: T(n) = n+1 = O(n).
Wouldn't the answer be O(n2) for a left or right skewed binary tree?