gistfile1.java

import java.io.*;

public class Solution {

     private class Node {
	  private Node left;
	  private Node right;
	  private int distLeft;
	  private int distRight;
	  private int distTop;
	  private int value;

	  public Node(int value) {
	       left = right = null;
	       distLeft = distRight = distTop = 0;
	       this.value = value;
	  }
     }

     private Node root;
     private int k;
     private int mx;

     private void dfs1(Node node) {
	  if (node.left != null) {
	       dfs1(node.left);
	       node.distLeft = Math.max(node.left.distLeft, node.left.distRight) + 1;
	  }
	  if (node.right != null) {
	       dfs1(node.right);
	       node.distRight = Math.max(node.right.distLeft, node.right.distRight) + 1;
	  }
     }

     private void dfs2(Node node, int distTop) {
	  if (node == null) {
	       return;
	  }
	  node.distTop = distTop;
	  if (node.distTop + node.distLeft < k &&
	      node.distTop + node.distRight < k &&
	      node.distLeft + node.distRight < k) {
	       mx = Math.max(node.value, mx);
	  }
	  dfs2(node.left, Math.max(node.distRight, node.distTop) + 1);
	  dfs2(node.right, Math.max(node.distLeft, node.distTop) + 1);
     }

     private void deleteNodeWithoutChildren(Node node, Node parent) {
	  if (parent.left == node) {
	       parent.left = null;
	  } else {
	       parent.right = null;
	  }
     }

     private void deleteNodeWithOneChild(Node node, Node parent) {
	  Node child = node.left == null ? node.right : node.left;
	  if (parent.left == node) {
	       parent.left = child;
	  } else {
	       parent.right = child;
	  }
     }

     private void deleteNodeWithTwoChildren(Node node) {
	  Node subParent;
	  Node sub;
	  if (node.right.left == null) {
	       subParent = node;
	       sub = node.right;
	  } else {
	       subParent = node.right;
	       while (subParent.left != null && subParent.left.left != null) {
		    subParent = subParent.left;
	       }
	       sub = subParent.left;
	  }
// 	  System.out.println("Removing 2:\n\tNode: " + node.value + "\n\tSub: " + sub.value + "\n\tSubParent: " + subParent.value);
	  node.value = sub.value;
	  if (sub.right == null) {
	       deleteNodeWithoutChildren(sub, subParent);
	  } else {
	       deleteNodeWithOneChild(sub, subParent);
	  }
     }

     private void removeNode(int value) {
	  if (root.value == value) {
	       if (root.left == null && root.right == null) {
		    root = null;
	       } else if (root.left == null) {
		    root = root.right;
	       } else if (root.right == null) {
		    root = root.left;
	       } else {
		    deleteNodeWithTwoChildren(root);
	       }
	  } else {
	       Node parent = root;
	       Node node; 
	       while ( (node = parent.value > value ? parent.left : parent.right).value != value) {
		    parent = node;
	       }
// 	       System.out.println("Node: " + node.value + " Parent: " + parent.value);
	       if (node.left == null && node.right == null) {
		    deleteNodeWithoutChildren(node, parent);
	       } else if (node.left == null || node.right == null) {
		    deleteNodeWithOneChild(node, parent);
	       } else {
		    deleteNodeWithTwoChildren(node);
	       }
	  }
     }
	  
	  
     
     private void addNode(Node curNode, Node newNode) {
	  if (curNode == null) {
	       root = newNode;
	  } else {
	       if (curNode.value > newNode.value) {
		    if (curNode.left == null) {
			 curNode.left = newNode;
		    } else {
			 addNode(curNode.left, newNode);
		    }
	       } else if (curNode.value < newNode.value) {
		    if (curNode.right == null) {
			 curNode.right = newNode;
		    } else {
			 addNode(curNode.right, newNode);
		    }
	       }
	  }
     }

     private void printTree(Node node, PrintWriter writer) {
	  if (node == null) {
	       return;
	  }
	  writer.println(node.value);
	  printTree(node.left, writer);
	  printTree(node.right, writer);
     }

     private void solve() throws Exception {
	  mx = -1;
	  BufferedReader reader = new BufferedReader(new FileReader("tst.in"));
	  k = Integer.parseInt(reader.readLine().trim());
	  while (reader.ready()) {
	       addNode(root, new Node(Integer.parseInt(reader.readLine().trim())));
	  }
	  reader.close();
	  PrintWriter writer = new PrintWriter(new FileWriter("tst.out"));
	  if (root != null) {
	       dfs1(root);
	       dfs2(root, 0);
	  }
	  if (mx != -1) {
	       removeNode(mx);
	  }
	  if (root == null) {
	       writer.println("Empty");
	  } else {
	       printTree(root, writer);
	  }
	  writer.close();
     }

     public static void main(String[] args) throws Exception {
	  new Solution().solve();
     }
}