Условие 
Найти пути минимальной длины между корнем и листьями и удалить средние по значению вершины этих путей (левым удалением), если они существуют .
Замечание.
Если некоторая вершина является средней по значению для нескольких путей минимальной длины, то удаляется она только один раз.(см. Пример 2).


Входные данные 
tst.in содержит последовательность чисел — ключей дерева.

Выходные данные 
tst.out содержит массив вершин, полученный прямым левым обходом итогового дерева.

Пример
tst.in
10
15
13
18
5
8
3

tst.out
10
3
18


import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.TreeSet;

import static java.lang.System.out;

/**
 * Created by IntelliJ IDEA.
 * User: Andrew
 * Date: 12.02.2011
 * Time: 19:53:21
 * To change this template use File | Settings | File Templates.
 */


public class Solution {
	interface Position {
		public int element();
	}

	static class LinkedBinaryTree {
		public void setMinLen(int minLen) {
			this.minLen = minLen;
		}

		public void setCurLen(int curLen) {
			this.curLen = curLen;
		}

		public ArrayList<Integer> arrayOfLeafs = new ArrayList<Integer>();
		public int minLen;
		public int curLen;

		class BTNode implements Position {
			private int element;
			private BTNode left, right;

			public BTNode(int el, BTNode l, BTNode r) {
				setElement(el);
				setLeft(l);
				setRight(r);
			}

			public int element() {
				return element;
			}

			public void setElement(int el) {
				element = el;
			}

			public BTNode getLeft() {
				return left;
			}

			public void setLeft(BTNode v) {
				left = v;
			}

			public BTNode getRight() {
				return right;
			}

			public void setRight(BTNode v) {
				right = v;
			}
		}

		private Position root; // reference to the root
		private int size; // number of nodes

		public LinkedBinaryTree() {
			root = null;
			size = 0;
		}

		public LinkedBinaryTree(int rootEl) {
			root = new BTNode(rootEl, null, null);
			size = 1;
		}

		public int size() {
			return size;
		}

		public boolean isEmpty() {
			return (size == 0);
		}

		public boolean isExternalLeft(Position v) {
			return (((BTNode) v).getLeft() == null);
		}

		public boolean isExternalRight(Position v) {
			return (((BTNode) v).getRight() == null);
		}

		public boolean isRoot(Position v) {
			return (v == root());
		}

		public Position root() {
			return root;
		}

		public Position leftChild(Position v) {
			return ((BTNode) v).getLeft();
		}

		public Position rightChild(Position v) {
			return ((BTNode) v).getRight();
		}

		private int setElement(Position v, int o) {
			int temp = ((BTNode) v).element();
			((BTNode) v).setElement(o);
			return temp;
		}

		private void expandExternalLeft(Position v) {
			if (isExternalLeft(v)) {
				((BTNode) v).setLeft(new BTNode(0, null, null));
				size++;
			}
		}

		private void expandExternalRight(Position v) {
			if (isExternalRight(v)) {
				((BTNode) v).setRight(new BTNode(0, null, null));
				size++;
			}
		}

		private void addElementFromRoot(Position pos, int el) {
			if (pos != null) {
				if (pos.element() == el)
					return;
				else {
					if (pos.element() < el) {
						if (isExternalRight(pos)) {
							expandExternalRight(pos);
							setElement(rightChild(pos), el);
						} else {
							addElementFromRoot(rightChild(pos), el);
						}
					} else {
						if (pos.element() > el) {
							if (isExternalLeft(pos)) {
								expandExternalLeft(pos);
								setElement(leftChild(pos), el);
							} else {
								addElementFromRoot(leftChild(pos), el);
							}
						}
					}
				}
			} else {
				root = new BTNode(el, null, null);
				size++;
			}
		}


		private void rootLeftRightFromRoot(Position pos, StringBuilder outString) {
			if (pos == null) {
				return;
			}
			outString.append(pos.element()+"\r\n");
			if (leftChild(pos) != null)
				rootLeftRightFromRoot(leftChild(pos), outString);
			if (rightChild(pos) != null)
				rootLeftRightFromRoot(rightChild(pos), outString);
		}


		public void addElement(int el) {
			addElementFromRoot(root(), el);
		}

		public void deleteElement(int el) {
			Position x = root, y = null;

			while (x != null) {
				if (el == x.element()) {
					break;
				} else {
					y = x;
					if (el < x.element()) {
						x = ((BTNode) x).getLeft();
					} else {
						x = ((BTNode) x).getRight();
					}
				}

			}

			if (x == null)
				return;

			if (((BTNode) x).getLeft() == null) {
				if (y == null) {
					root = ((BTNode) x).getLeft();
				} else {
					if (x == ((BTNode) y).getRight()) {
						((BTNode) y).setRight(((BTNode) x).getRight());
					} else {
						((BTNode) y).setLeft(((BTNode) x).getRight());
					}
				}
			} else {
				Position leftMost = ((BTNode) x).getLeft();
				y = null;
				while (((BTNode) leftMost).getRight() != null) {
					y = leftMost;
					leftMost = ((BTNode) leftMost).getRight();
				}
				if (y != null) {
					((BTNode) y).setRight(((BTNode) leftMost).getLeft());
				} else {
					((BTNode) x).setLeft(((BTNode) leftMost).getLeft());
				}
				((BTNode) x).setElement((leftMost).element());
			}
		}

		public void rootLeftRight(String path) throws IOException {
			FileOutputStream fos = new FileOutputStream(path);
			DataOutputStream dos = new DataOutputStream(fos);
			StringBuilder temp = new StringBuilder();

			rootLeftRightFromRoot(root(), temp);

			dos.writeBytes(temp.toString());

		}

		public void assistRootLeftRight(Position pos) {
			if (pos == null) {
				return;
			}

			curLen++;
			if (rightChild(pos) == null && leftChild(pos) == null) {
				if (curLen == minLen) {
					arrayOfLeafs.add(pos.element());
				}
				if (curLen < minLen) {
					minLen = curLen;
					arrayOfLeafs.clear();
					arrayOfLeafs.add(pos.element());
				}
			}
			if (leftChild(pos) != null) {
				assistRootLeftRight(leftChild(pos));
			}
			if (rightChild(pos) != null) {
				assistRootLeftRight(rightChild(pos));
			}

			curLen--;

		}

		public void findAndDeleteElements() {
			if (minLen % 2 != 0) {
				TreeSet<Integer> setOfNodesToDelete = new TreeSet<Integer>();
				for (Integer li : arrayOfLeafs) {
					Position pos = root;
					ArrayList<Integer> tempArray = new ArrayList<Integer>();

					while (li != pos.element()) {
						tempArray.add(pos.element());
						if (li > pos.element())
							pos = ((BTNode) pos).getRight();
						else if (li < pos.element()) {
							pos = ((BTNode) pos).getLeft();
						}
					}
					tempArray.add(li);

					Collections.sort(tempArray);
					setOfNodesToDelete.add(tempArray.get(minLen / 2));
				}

				for (Integer li : setOfNodesToDelete) {
					this.deleteElement(li);
				}
			}
		}
	}
	public static void main(String[] args) {

		LinkedBinaryTree tree = new LinkedBinaryTree();

		FileInputStream fis = null;
		try {
			fis = new FileInputStream("tst.in");
			BufferedReader br = new BufferedReader(new InputStreamReader(fis));
			String newLine;
			while ((newLine = br.readLine()) != null){
				tree.addElement(Integer.parseInt(newLine));
			}

			tree.setCurLen(0);
			tree.setMinLen(tree.size());

			tree.assistRootLeftRight(tree.root());
			tree.findAndDeleteElements();
			tree.rootLeftRight("tst.out");


		} catch (FileNotFoundException e) {
			out.println("No Such File");  //To change body of catch statement use File | Settings | File Templates.
		} catch (IOException e) {
			out.println("File Exception");  //To change body of catch statement use File | Settings | File Templates.
		}
	}
}