BST tree- running time

Question

I have a pseudo- code:

function func(BST t):
    x = MIN(t)
    for i=1..n do:
        print x.key
        x = SUCCESSOR(x)

Now, I need to prove it's runnig time is THETA(n). BUT, I know SUCCESSOR running time is O(logn), and therefor running time is O(nlogn). where is my mistake here?

Thank in advance...

Answer 1

There are two possibilities:

• This not true, the run time is O(nlogn)
• You know the exact implementation of SUCCESSOR, which has upper bounded logarithmic complexity (as stated, O(logn)), but you can deduce, that when performing it one after another it actually degenerates to theta(1). In fact, good implementation of SUCCESSOR in BST should have amortized theta(1) complexity as each node will be visited at most twice during the whole func execution.

Answer 2

It really depends on the implementation of your BST, but if your BST holds a 'father' node, and is using it to find the successor, it will need to traverse each edge at most twice - once one you go "down", the first time to the node, and one when you go "up", back from it.

Since a tree has n-1 edges, you get at most 2*(n-1) number edges read, and this is O(n).

Note that indeed the worst case of the SUCCESSOR() function is O(logn), but the average case is O(1), if it is implemented the way I described.