What is the time complexity of TreeSet iteration?

Question

In my code, Java TreeSet iteration is the dominant time factor. In looking at the system I believe that it is O(n) complexity. Can anyone verify this?

I am thinking that by providing links backward from child node to parent node I could improve the performance.

Answer 1

TreeSet iteration is of course O(n), as can be expect from any sensible tree-walking algorithm.

I am thinking that by providing links backward from child node to parent node I could improve the performance.

TreeMap (which TreeSet is based on) already has such parent references. This is the method it all boils down to:

private Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}