Remove duplicate infinite integer

Remove duplicates from infinite integers

Problem

You are given an infinite stream of integers. The stream of integers is unsorted and are provided by iterator so that you don't have the access to all the elements at once. You have to return another iterator from the input iterator so that there are no duplicates and the input order is maintained.

Solution

We will use binary search tree to have a O(n log n) solution. Each number is inserted into an inner binary search tree and if no previous existence found, it is added to output stream. The output iterator always prepare the next element beforehand so that hasNext and next does not disagree. When the input iterator finishes so does the output. This has worst case complexity of O(n^2) for a sorted input sequence, we can improve this by any of the balanced search tree like red black tree.

Code

import java.util.Iterator;

public class RemoveDuplicateBST
{
 public static void main(String[] args)
 {
  System.out.println("Input\tOutput");
  Iterator inputIterator = new InputIterator(30);
  Iterator outputIterator = new OutputIterator(inputIterator);
  while (outputIterator.hasNext())
  {
   System.out.println("\t<<" + outputIterator.next());
  }
 }

 private static class InputIterator implements Iterator
 {
  int count;

  public InputIterator(int count)
  {
   this.count = count;
  }

  @Override
  public boolean hasNext()
  {
   return count != 0;
  }

  @Override
  public Integer next()
  {
   int input = (int) (Math.random() * 30);
   System.out.println(">>" + input);
   count--;
   return input;
  }

  @Override
  public void remove()
  {

  }
 }

 private static class OutputIterator implements Iterator
 {
  Iterator inputIterator;
  Integer nextElement;
  Node root;

  public OutputIterator(Iterator inputIterator)
  {
   this.inputIterator = inputIterator;
   if (inputIterator.hasNext())
   {
    nextElement = inputIterator.next();
    if (nextElement != null)
     add(nextElement);
   }
  }

  private boolean add(int value)
  {
   return add(root, value);
  }

  private boolean add(Node current, int value)
  {
   Node node = new Node(value);
   if (current == null)
   {
    root = node;
    return true;
   }
   if (current.value == value)
   {
    return false;
   }
   if (current.value > value)
   {
    if (current.left == null)
    {
     current.left = node;
     return true;
    } else
    {
     return add(current.left, value);
    }
   } else
   {
    if (current.right == null)
    {
     current.right = node;
     return true;
    } else
    {
     return add(current.right, value);
    }
   }
  }

  @Override
  public boolean hasNext()
  {
   return nextElement != null;
  }

  @Override
  public Integer next()
  {
   int output = nextElement;
   nextElement = null;
   while (inputIterator.hasNext())
   {
    int input = inputIterator.next();
    if (add(input))
    {
     nextElement = input;
     break;
    }
   }
   return output;
  }

  @Override
  public void remove()
  {

  }
 }

 private static class Node
 {
  int value;
  Node left;
  Node right;

  public Node(int value)
  {
   this.value = value;
  }
 }
}