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