package algodataufg04_a_j;

class Tree {
	private class Node {
		public int key;
		public Node left = null;
		public Node right = null;

			public Node() {
			}

		public Node(int key, Node l, Node r) {
			this.key = key;
			this.left = l;
			this.right = r;
		}
	}

	public Node root;

	public void insert(int x) {
		if (root == null) {
			root = new Node(x, null, null);
		} else {
			insert(x, root);
		}
	}

	public void insert(int x, Node n) {
		if ((countNodes(n.left)) < (countNodes(n.right))) {
			if (n.left != null) {
				insert(x, n.left);
			} else {
				n.left = new Node(x, null, null);
			}
		} else {
			if (n.right != null) {
				insert(x, n.right);
			} else {
				n.right = new Node(x, null, null);
			}
		}
	}

	/*public int size(Node n) {
		if (n == null) {
			return 0;
		} else if ((n.left == null) && (n.right == null)) {
			return 1;
		} else {
			int l = size(n.left);
			int r = size(n.right);
			//if (l <= r) {
				//return l + 1;
			//} else {
				//return r + 1;
			//}
			return ((l <= r) ? (l+1) : (r+1));
		}
	}*/

	public int countNodes(Node n) {
		if ( n == null ) {
			return 0;
		} else {
			int count = 1;
			count += countNodes(n.left);
			count += countNodes(n.right);

			return count;
		}
	}

	public void lwr(final Node w) {         //Inorder
		if (w != null) {
			lwr(w.left);
			System.out.print(w.key+" ");
			lwr(w.right);
		}
	}

	public void rwl(final Node w) {         //Inorder
		if (w != null) {
			rwl(w.right);
			System.out.print(w.key+" ");
			rwl(w.left);
		}
	}

	public void rwlGraph(final Node w, int depth, char LWR) {
		if (w != null) {
			rwlGraph(w.right, ++depth, 'R');
			for (int i = 0; i < depth; i++)
				System.out.print("   ");
			switch (LWR) {
			case 'L':
				System.out.print("\\");
				break;
			case 'W':
				System.out.print(" ");
				break;
			case 'R':
				System.out.print("/");
			}
			System.out.println(w.key);
			rwlGraph(w.left, depth, 'L');
		}
	}

	public void wrl(final Node w) {             //Preorder
		if (w != null) {
			System.out.print(w.key+" ");
			wrl(w.right);
			wrl(w.left);
		}
	}

	public void lrw(final Node w) {             //Postorder
		if (w != null) {
			lrw(w.left);
			lrw(w.right);
			System.out.print(w.key+" ");
		}
	}

	public void rlw(final Node w) {             //Postorder
		if (w != null) {
			rlw(w.right);
			rlw(w.left);
			System.out.print(w.key+" ");
		}
	}

	public void wlr(final Node w) {             //Preorder
		if (w != null) {
			System.out.print(w.key+" ");
			wlr(w.left);
			wlr(w.right);
		}
	}

}