public class BinaryTree {

    private Subtree root = null;

    public BinaryTree() { }

    public BinaryTree(int value) {
	root = new Subtree(value);
    }
    
   /**
    * insert a new node with 
    * a given key and eliminate duplicates
    * @param value - the value of the key to insert
    */
    public void insert(int value) {
	Subtree x = root;
	Subtree y = null;
	while (x != null) {
	    y = x;
	    if (value < x.value())
		x = x.left();
	    else 
		x = x.right();
	}
	if (y == null) {
	    root = new Subtree(value);
	} else {
	    if (value != y.value()) {
		Subtree z = new Subtree(value);
		z.parent(y);
		if (value < y.value())
		    y.left(z);
		else
		    y.right(z);
	    }
	}
    }

    /**
     * lookup a Subtree with a given key
     * @param value - the value of the Subtree to lookup
     */
    public Subtree lookup(int value) {
	return lookup(value, root);
    }

    /**
     * print an ordered sequence
     * of the keys stored in the tree
     */
    public void printOrdered() {
	printOrdered(root);
    }
    
    /**
     * print the structure of the tree
     */
    public void printStructure() {
	printStructure(root);
    }

    private Subtree lookup(int value, Subtree x) {
	if (x == null)
	    return null;
	if (value == x.value())
	    return x;
	if (value < x.value())
	    return lookup(value, x.left());
	else 
	    return lookup(value, x.right());	   
    }
    
    private void printOrdered(Subtree x) {
	if (x.left() != null)
	    printOrdered(x.left());
	System.out.print(x.value()); 
	if (x.right() != null)
	    printOrdered(x.right());
    }
    
    private void printStructure(Subtree a) {
	int level = 0;
	Subtree p = null;
	while (a != null) {
	    if (p == a.parent()) {
		for (int i = 0; i<level; ++i) System.out.print(" ");
		System.out.println(a.value());
		p = a;
		if (a.left() != null) {
		    a = a.left(); ++level;
		} else if (a.right() != null) {
		    a = a.right(); ++level;
		} else {
		    a = a.parent(); --level;
		}
	    } else if (p == a.left() && a.right() != null) {
		p = a;
		a = a.right(); ++level;
	    } else {
		p = a;
		a = a.parent(); --level;
	    }
	}
    }

    public static void main(String[] args) {
	BinaryTree myTree = new BinaryTree();
	myTree.insert(2);
	myTree.insert(1);
	myTree.insert(4);
	myTree.insert(0);
	myTree.insert(3);
	myTree.printStructure();
    }


    /**
     * private helper class which is a single node
     * represented trough an integer key,
     * a parent, left and right subtree pointer.
     */
    private class Subtree {
	private int value;
	private Subtree parent;
	private Subtree left;
	private Subtree right;

	public Subtree(int value) { value(value); }

	public int  value() { return value; }
	public void value(int value) { this.value = value; }

	public Subtree parent() { return parent; }
	public void parent(Subtree parent) { this.parent = parent; }

	public Subtree left() { return left; }
	public void left(Subtree left) { this.left = left; }

	public Subtree right() { return right; }
	public void right(Subtree right) { this.right = right; }

    }

}