Week-12 - Midterm II: Solutions

Problem 1:

In order to get a worst case running time of O(n^2), we should draw a tree in such a way that, depth() function is called at each level. Therefore, a tree with many leaves will run for the worst case.

Problem 2

ArrayList : O(n) for remove => O(n^2) run-time.
LinkedList: O(1) for remove => O(n) run-time

Reference: ArrayList Vs LinkedList

Problem 3

Code

Problem 4

Inorder and Breadth first traversal.

Problem 5

Code