   Type like pro

# 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)
}
}

{
}

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
{
}
} else
{
if (current.right == null)
{
current.right = node;
return true;
} else
{
}
}
}

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

@Override
public Integer next()
{
int output = nextElement;
nextElement = null;
while (inputIterator.hasNext())
{
int input = inputIterator.next();
{
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;
}
}
}

```