ImmutableBinaryTree_part1.java

public class ImmutableBinaryTree<T extends Comparable<T>> implements ImmutableSet<T> {

	private final ImmutableBinaryTree<T> left;
	private final ImmutableBinaryTree<T> right;
	private final T value;
	
	public ImmutableBinaryTree(ImmutableBinaryTree<T> left,
			ImmutableBinaryTree<T> right, T value) {
		this.left = left;
		this.right = right;
		this.value = value;
	}

ImmutableBinaryTree_part2.java

@Override
public ImmutableBinaryTree<T> add(T element) {
	if ( value.compareTo(element) == 0 ) {
		return this; // Element already exists
	}
	return addSubtree(new ImmutableBinaryTree<T>(null, null, element));
}

private ImmutableBinaryTree<T> addSubtree( ImmutableBinaryTree<T> subTree ) {
	if ( subTree == null )
	{
		return this;
	}
	if ( value.compareTo(subTree.value) == 0 ) {
		// Need to merge subTree children with this tree's children
		final ImmutableBinaryTree<T> newLeft = left !=null ? left.addSubtree(subTree.left) : subTree.left;
		final ImmutableBinaryTree<T> newRight = right !=null ? right.addSubtree(subTree.right) : subTree.left;
		return new ImmutableBinaryTree<T>(newLeft, newRight, value);
	} else if ( value.compareTo(subTree.value) < 0 ) {
		// Element goes on right subtree
		if ( right != null ) {
			return new ImmutableBinaryTree<T>(left, right.addSubtree(subTree), value);
		} else {
			return new ImmutableBinaryTree<T>(left, subTree, value);
		}
	} else {
		// Element goes on left subtree
		if ( left != null ) {
			return new ImmutableBinaryTree<T>(left.addSubtree(subTree), right, value);	
		} else {
			return new ImmutableBinaryTree<T>(subTree, right, value);
		}
	}	
}

ImmutableBinaryTree_part3.java

@Override
public ImmutableBinaryTree<T> remove(T element) {
	if ( value.compareTo(element) == 0 ) {
		if ( left == null && right == null )
			return null;
		if ( left == null ) return right;
		if ( right == null ) return left;
		return left.addSubtree(right);
	}
	if ( value.compareTo(element) < 0 && right != null ) {
		return new ImmutableBinaryTree<T>(left, right.remove(element), value);
	}
	else if ( value.compareTo(element) > 0 && left != null ) {
		return new ImmutableBinaryTree<T>(left.remove(element), right, value);
	}
	return this; // Element not found
}

ImmutableBinaryTree_part4.java

@Override
public boolean contains(T element) {
	if ( value.equals( element) ) {
		return true;
	}
	else if ( value.compareTo(element) < 0 ) {
		return right == null ? false : right.contains(element);
	}
	else {
		return left == null ? false : left.contains(element);
	}
}

ImmutableBinaryTree_part5.java

@Override
public List<T> toList() {
	final List<T> asList = new LinkedList<T>();
	if ( left != null ) { asList.addAll(left.toList()); }
	asList.add(value);
	if ( right != null ) { asList.addAll(right.toList()); }
	return asList;
}

ImmutableBinaryTree_part6.java

@Override
public String toString() {
	return innerToString("");
}
	
private String innerToString( String prefix ) {
	StringBuilder builder = new StringBuilder();
	if ( left != null ) {
		builder.append( left.innerToString(prefix + " "));
	}
	builder.append(prefix).append(value).append("\n");
	if ( right != null ) {
		builder.append( right.innerToString(prefix + " "));
	}
	return builder.toString();
}

ImmutableSet.java

import java.util.List;

public interface ImmutableSet<T extends Comparable<T>> {
	ImmutableSet<T> add( T element );
	
	ImmutableSet<T> remove( T element );
	
	boolean contains( T element );
	
	List<T> toList();
}

ImmutableTreeRunner.java

import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public final class ImmutableTreeRunner {

	private static final Random RANDOM = new Random();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		final Integer firstValue = Integer.valueOf( RANDOM.nextInt(1000));
		
		ImmutableSet<Integer> immutableSet = new ImmutableBinaryTree<Integer>(null, null, firstValue);
		final Set<Integer> mutableSet = new TreeSet<Integer>();
		mutableSet.add(firstValue);

		// Add 100 random integers in the [0,1000) range
		for  ( int i = 0; i < 100; i++ )
		{
			final int value = RANDOM.nextInt(1000);
			mutableSet.add(value);
			immutableSet = immutableSet.add(value);
		}
		List<Integer> immutableValues = immutableSet.toList();
		System.out.println( immutableValues.toString() );
		System.out.println( mutableSet.toString() );

		// Remove 100 random integers in the [0,1000) range
		for ( int i = 0; i < 100; i++ )
		{
			final int value = RANDOM.nextInt(1000);
			mutableSet.remove( value );
			immutableSet = immutableSet.remove(value);
		}
		immutableValues = immutableSet.toList();
		assert( immutableValues.size() == mutableSet.size() );
		Iterator<Integer> immutableValueIter = immutableValues.iterator();
		Iterator<Integer> mutableValueIter = mutableSet.iterator();
		System.out.println( immutableValues.toString() );
		System.out.println( mutableSet.toString() );
		
		while ( true ) {
			assert( immutableValueIter.hasNext() == mutableValueIter.hasNext() );
			if ( immutableValueIter.hasNext() != mutableValueIter.hasNext() ) throw new RuntimeException("hasNext doesn't match");
			if ( !immutableValueIter.hasNext() ) { break; }
			final Integer immutableVal = immutableValueIter.next();
			final Integer mutableVal = mutableValueIter.next();
			assert( immutableVal.equals(mutableVal));
		}
		
		System.out.println(immutableSet.toString());
	}

}