import java.util.Random;
 
class Indirect {
  Integer data;
  Indirect() { data = null; }
}
 
class Node {
  private Integer data;
  private Node left;
  private Node right;
  private Node(Integer data) {
    this.data = data;
    this.left = this.right = null;
  }
  public static Node pushNode(Node root, Integer data) {
    if (root == null) {
      return new Node(data);
    } else if (data.intValue() < root.data.intValue()) {
      root.left = pushNode(root.left, data);
      return root;
    } else {
      root.right = pushNode(root.right, data);
      return root;
    }
  }
  public static Node popNode(Node root, Indirect idata) {
    if (root == null) {
      idata = null;
      return null;
    }
    if (root.left != null) {
      root.left = popNode(root.left, idata);
      return root;
    }
    idata.data = root.data;
    return root.right;
  }
}
 
class BinTree {
  private Node root;
  BinTree() { root = null; }
  void pushNode(Integer data) { root = Node.pushNode(root, data); }
  Integer popNode() {
    Indirect idata;
    root = Node.popNode(root, idata = new Indirect());
    if (root == null && idata == null)
      return null;
    return idata.data;
  }
}
 
class Main {
  final static int N = 10;
  final static int MAX = 10000;
  public static void main(String[] args) {
    Random random = new Random();
    BinTree root = new BinTree();
    Integer data;
    for (int i = 0; i < N; i++) {
      data = new Integer(random.nextInt(MAX));
      root.pushNode(data);
      System.out.println(data);
    }
    System.out.println();
 
    while ((data = root.popNode()) != null) {
      System.out.println(data);
    }
  }
}
/* end */
 

aW1wb3J0IGphdmEudXRpbC5SYW5kb207CgpjbGFzcyBJbmRpcmVjdCB7CiAgSW50ZWdlciBkYXRhOwogIEluZGlyZWN0KCkgeyBkYXRhID0gbnVsbDsgfQp9CgpjbGFzcyBOb2RlIHsKICBwcml2YXRlIEludGVnZXIgZGF0YTsKICBwcml2YXRlIE5vZGUgbGVmdDsKICBwcml2YXRlIE5vZGUgcmlnaHQ7CiAgcHJpdmF0ZSBOb2RlKEludGVnZXIgZGF0YSkgewogICAgdGhpcy5kYXRhID0gZGF0YTsKICAgIHRoaXMubGVmdCA9IHRoaXMucmlnaHQgPSBudWxsOwogIH0KICBwdWJsaWMgc3RhdGljIE5vZGUgcHVzaE5vZGUoTm9kZSByb290LCBJbnRlZ2VyIGRhdGEpIHsKICAgIGlmIChyb290ID09IG51bGwpIHsKICAgICAgcmV0dXJuIG5ldyBOb2RlKGRhdGEpOwogICAgfSBlbHNlIGlmIChkYXRhLmludFZhbHVlKCkgPCByb290LmRhdGEuaW50VmFsdWUoKSkgewogICAgICByb290LmxlZnQgPSBwdXNoTm9kZShyb290LmxlZnQsIGRhdGEpOwogICAgICByZXR1cm4gcm9vdDsKICAgIH0gZWxzZSB7CiAgICAgIHJvb3QucmlnaHQgPSBwdXNoTm9kZShyb290LnJpZ2h0LCBkYXRhKTsKICAgICAgcmV0dXJuIHJvb3Q7CiAgICB9CiAgfQogIHB1YmxpYyBzdGF0aWMgTm9kZSBwb3BOb2RlKE5vZGUgcm9vdCwgSW5kaXJlY3QgaWRhdGEpIHsKICAgIGlmIChyb290ID09IG51bGwpIHsKICAgICAgaWRhdGEgPSBudWxsOwogICAgICByZXR1cm4gbnVsbDsKICAgIH0KICAgIGlmIChyb290LmxlZnQgIT0gbnVsbCkgewogICAgICByb290LmxlZnQgPSBwb3BOb2RlKHJvb3QubGVmdCwgaWRhdGEpOwogICAgICByZXR1cm4gcm9vdDsKICAgIH0KICAgIGlkYXRhLmRhdGEgPSByb290LmRhdGE7CiAgICByZXR1cm4gcm9vdC5yaWdodDsKICB9Cn0KCmNsYXNzIEJpblRyZWUgewogIHByaXZhdGUgTm9kZSByb290OwogIEJpblRyZWUoKSB7IHJvb3QgPSBudWxsOyB9CiAgdm9pZCBwdXNoTm9kZShJbnRlZ2VyIGRhdGEpIHsgcm9vdCA9IE5vZGUucHVzaE5vZGUocm9vdCwgZGF0YSk7IH0KICBJbnRlZ2VyIHBvcE5vZGUoKSB7CiAgICBJbmRpcmVjdCBpZGF0YTsKICAgIHJvb3QgPSBOb2RlLnBvcE5vZGUocm9vdCwgaWRhdGEgPSBuZXcgSW5kaXJlY3QoKSk7CiAgICBpZiAocm9vdCA9PSBudWxsICYmIGlkYXRhID09IG51bGwpCiAgICAgIHJldHVybiBudWxsOwogICAgcmV0dXJuIGlkYXRhLmRhdGE7CiAgfQp9CgpjbGFzcyBNYWluIHsKICBmaW5hbCBzdGF0aWMgaW50IE4gPSAxMDsKICBmaW5hbCBzdGF0aWMgaW50IE1BWCA9IDEwMDAwOwogIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgIFJhbmRvbSByYW5kb20gPSBuZXcgUmFuZG9tKCk7CiAgICBCaW5UcmVlIHJvb3QgPSBuZXcgQmluVHJlZSgpOwogICAgSW50ZWdlciBkYXRhOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgZGF0YSA9IG5ldyBJbnRlZ2VyKHJhbmRvbS5uZXh0SW50KE1BWCkpOwogICAgICByb290LnB1c2hOb2RlKGRhdGEpOwogICAgICBTeXN0ZW0ub3V0LnByaW50bG4oZGF0YSk7CiAgICB9CiAgICBTeXN0ZW0ub3V0LnByaW50bG4oKTsKICAgIAogICAgd2hpbGUgKChkYXRhID0gcm9vdC5wb3BOb2RlKCkpICE9IG51bGwpIHsKICAgICAgU3lzdGVtLm91dC5wcmludGxuKGRhdGEpOwogICAgfQogIH0KfQovKiBlbmQgKi8K