title: Java iterate on a TreeMap/TreeSet in O(N) and remove other elements than current one
body: <p>Is there a way to iterate through a TreeSet/TreeMap in O(N) while being able to remove an other entry than the one the iterator currently points to?</p>
  
  <p>Here is a simple example using a TreeSet. The set contains positive integers and I check if it's possible to create N/2 pairs such as each pairs contains [x, 2*x]. I iterate through the map from the lowest key, check if we find the double and remove it when found. 
  <em>To be clear, this example is just to illustrate, I don't need to find a solution to the example itself, but to know if I can remove while iterating.</em></p>
  
  <pre><code> public boolean checkTree(TreeSet&lt;Integer&gt; tree){
          for (Integer i: tree) {
                  int twice = i*2;
                  if(!tree.contains(twice)) return false;
                  else tree.remove(twice);
          }
          return true;
  }
  </code></pre>
  
  <p>Of course, if I'll do that, I will get a <em>ConcurrentModificationException</em>, because I remove an element without using <em>iterator.remove()</em>. But I can't use that method because I would like to remove an other element.</p>
  
  <p>Here is one workaround that I can think of:</p>
  
  <pre><code> public boolean checkTree(TreeSet&lt;Integer&gt; tree){
          while (tree.size() &gt; 0) {
                  int twice = tree.pollFirst()*2;
                  if(!tree.contains(twice)) return false;
                  else tree.remove(twice);
          }
  
          return true;
      }
  </code></pre>
  
  <p>But it will execute slower because calling N times <em>pollFirst()</em> is O(N log N) instead of the O(N) of the treeIterator. The overall complexity will indeed remain the same because of the <em>contains()</em> and <em>remove()</em> calls.</p>
  
  <p>Is there a way to remove while still iterating through the tree using the inorder traversal? There is a <em>successor()</em> method in TreeMap class but it's not public.
  This question could actually apply to all NavigableSet/NavigableMap .</p>