Question

Given the following find-min function, write the recurrence and solve it using the master theorem. Assume the worst case, i.e. the tree is imbalanced and skewed to the left.
int find_min (TreeNode* tree)
// returns the minimum value in a binary search tree
{ if (tree == NULL)
   throw (EmptyTreeException());
 else
  if (tree -> left == NULL)
     return(tree->info);
 else
 { return find_min(tree->left);
}
}

Answer 1

Recurrence relation:
---------------------
T(n) = T(n-1) + O(1) // Assuming that the tree is skewed to left.

This is not in the form of T(n) = aT(n/b) + f(n). so, we can not apply master's theorem to this recurrence relation.
so, solving the recurrence relation with iteration method.

T(n)
= T(n-1) + O(1)
= T(n-2) + + O(1) + O(1)
= T(1) + O(1) + ... + O(1) + O(1)
= O(1) + O(1) + ... + O(1) + O(1)
= n*O(1)
= O(n)

so, time complexity is O(n)