/**
 *
 *
 *  bjarneh@ifi.uio.no
 *
 */

class Main {


	public static void main (String[] args){
		
		int[] elms = {4,23,11,11,-11,100,1,11,11,2};

		BinNode r = new BinNode(5);
		for(int elm : elms){
			r.add2(elm);
		}

		r.printInfix();
		System.out.println("------------");
		r.printPrefix();
		System.out.println("------------");
		r.printPostfix();

	}


}


class BinNode {

	BinNode(int _data){
		this.data = _data;
	}


	int data;
	BinNode left;
	BinNode right;


	void printInfix(){
		if(left != null){
			left.printInfix();
		}

		System.out.println(this.data);
		
		if(right != null){
			right.printInfix();
		}
	}

	void printPostfix(){
		if(left != null){
			left.printPostfix();
		}
		if(right != null){
			right.printPostfix();
		}
		
		System.out.println(this.data);
	}

	void printPrefix(){
		System.out.println(this.data);
		
		if(left != null){
			left.printPrefix();
		}
		if(right != null){
			right.printPrefix();
		}
	}

    /**
	 * oppgave 4 a)
	 *
	 * */
	void add(int a){

		if(a == this.data){
			
			if(right == null){
				left = new BinNode(a);
			}else{
				left.add(a);
			}


		}else{

			if(a < this.data){
				if(left == null){
					left = new BinNode(a);
				}else{
					left.add(a);
				}
	
			}else if(a > this.data){
				if(right == null){
					right = new BinNode(a);	
				}else{ 
					right.add(a);
				}
			}
		}
	}




    /**
	 * oppgave 4 c)
	 *
	 * */

	void addEqual(int a){

	// just go to bottom of left subtree and add
		if(this.left != null){
			left.addEqual(a);
		}else{
			left = new BinNode(a);
		}
	}


    /**
	 * oppgave 4 c)
	 *
	 * */

	void add2(int a){


		if(a == this.data){

			if(right == null){
				right = new BinNode(a);
			}else if(right.data == this.data){
				right.addEqual(a);
			}else if(right.data != this.data){
				BinNode tmp = right;
				BinNode n_right = new BinNode(a);
				right = n_right;
				right.right = tmp;
			}


		}else{

			if(a < this.data){
				if(left == null){
					left = new BinNode(a);
				}else{
					left.add2(a);
				}
	
			}else if(a > this.data){
				if(right == null){
					right = new BinNode(a);	
				}else{ 
					right.add2(a);
				}
			}
		}
	}

    /**
	 * oppgave 4 d)
	 *
	 * */
	void fancyPrint(){
		//TODO
	}

}