Why is TreeSet Iteration O(n) instead of O(n*logn)?

Question

I read a previous question about the time complexity for TreeSet and the answer was that it takes O(n) time. However, I don't understand why it is O(n) to iterate instead of O(n*nlogn).

Each next call takes O(logn) time

So if I iterate through a TreeSet like this:

while (iterator.hasNext()){ //Runs N times
   System.out.println(iterator.next() + " "); //each next is O(logn)
}

I would expect for it to be O(n*logn) and not O(n) because the while loop has N iterations and each iterator.next() call takes O(logn) time.

Answer 1

The worst-case time for one next operation is O(log n) because that's the height of the tree. On average, however, the next element can be found in time O(1). This is because the whole traversal in essence uses each of the n-1 tree edges twice.