class Node {
    int  data;        // このノードが保持するデータ
    Node left=null;   // 左の部分木への参照
    Node right=null;  // 右の部分木への参照

    /* 「left以下の任意のデータ<= data <=right以下の任意のデータ」
    	となるように，データを挿入する．                          */
    public void insert (int data) {
    	if (data < this.data) { // 左へ挿入
    	    if (left == null) {
    	    	left = new Node();
    	    	left.data = data;
    	    } else {
    	    	left.insert(data);
    	    }
    	} else {        // 右へ挿入
    	    if (right == null) {
    	    	right = new Node();
    	    	right.data = data;
    	    } else {
    	    	right.insert(data);
    	    }
    	}
    }

    // 木の高さを計算
    public int height () {
    	int left_height=0, right_height=0;
    	if (left != null) {
    	    left_height = left.height();
    	}
    	if (right != null) {
    	    right_height = right.height();
    	}
    	return Math.max(left_height, right_height)+1;
    } 

    public void show (int depth) {
    	if (right!=null) right.show(depth+1);
    	for (int i=0; i<depth; i++) {
    	    System.out.print(" ");
    	}
    	System.out.println(data);
    	if (left!=null) left.show(depth+1);
    }

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

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

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

    public static void main (String[] args) {
    	Node root = new Node();
    	root.data = 10;
    	root.insert(15);
    	root.insert(5);
    	root.insert(12);
    	root.insert(8);
    	root.insert(9);

    	System.out.println(root.height());
    	root.show(0);
    	root.pre_order();
    	root.in_order();
    	root.post_order();
    }
}