import java.util.Random;

class BinTree {

  class Indirect {
    Integer data;
    Indirect() { data = null; }
  }

  static 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;
    }
  }

  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 */