import java.util.*;
import java.util.Scanner;
public class Exercise2504{
public static void main(String[] args){
BST tree = new BST();
Scanner input = new Scanner(System.in);
for (int i=0;i<10;i++){
tree.insert(input.nextInt());
}
tree.nonRecursivePreorder();
}
static class BST<E extends Comparable> extends AbstractTree{
protected TreeNode root;
protected int size = 0;
public BST(){
}
public BST(E[] objects){
for(int i=0;i<objects.length;i++)
insert(objects[i]);
}
@Override
public boolean search(E e){
TreeNode current= root;
while (current != null){
if(e.compareTo(current.element)<0){
current=current.left;
}else if(e.compareTo(current.element)>0){
current=current.right;
}else
return true;
}
return false;
}
@Override
public boolean insert(E e) {
if (root==null)
root = createNewNode(e);
else{
TreeNode parent =null;
TreeNode current = root;
while (current !=null)
if(e.compareTo(current.element)<0){
parent=current;
current=current.left;
}else if(e.compareTo(current.element)>0){
parent=current;
current=current.right;
}else
return false;
if(e.compareTo(parent.element)<0)
parent.left = createNewNode(e);
else
parent.right = createNewNode(e);
}
size++;
return true;
}
protected TreeNode createNewNode(E e){
return new TreeNode(e);
}
@Override
public void inorder(){
inorder(root);
}
protected void inorder(TreeNode root){
if (root == null)
return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}
@Override
public void postorder(){
postorder(root);
}
protected void postorder(TreeNode root){
if (root==null)
return;
postorder(root.left);
postorder(root.right);
System.out.print(root.element + " ");
}
@Override
public void preorder(){
preorder(root);
}
protected void preorder(TreeNode root){
if (root==null)
return;
System.out.print(root.element+ " ");
preorder(root.left);
preorder(root.right);
}
public static class TreeNode<E extends Comparable>{
protected E element;
protected TreeNode left;
protected TreeNode right;
public TreeNode(E e){
element =e;
}
}
@Override
public int getSize(){
return size;
}
public TreeNode getRoot(){
return root;
}
public java.util.ArrayList<TreeNode> path(E e){
java.util.ArrayList<TreeNode> list = new java.util.ArrayList<TreeNode>();
TreeNode current = root;
while (current !=null) {
list.add(current);
if(e.compareTo(current.element)<0){
current = current.left;
} else if(e.compareTo(current.element)>0){
current = current.right;
}else
break;
}
return list;
}
@Override
public boolean delete(E e){
TreeNode parent= null;
TreeNode current = root;
while (current !=null)
if(e.compareTo(current.element)<0){
parent=current;
current=current.left;
}else if(e.compareTo(current.element)>0){
parent=current;
current=current.right;
}else
break;
}
if (current==null){
return false;
if(current.left==null){
if(parent==null){
root = current.right;
}else{
if(e.compareTo(parent.element)<0)
parent.left=current.right;
else
parent.right=current.right;
}
}else{
TreeNode parentOfRightMost =current;
TreeNode rightMost = current.left;
while (rightMost.right != null){
parentOfRightMost = rightMost;
rightMost=rightMost.element;
if(parentOfRightMost.right==rightMost)
parentOfRightMost.right=rightMost.left;
else
parentOfRightMost.left=rightMost.left;
}
size--;
return ture;
}
@Override
public java.util.Iterator iterator(){
return new InorderIterator();
}
class InorderIterator implements java.util.Iterator{
private java.util.ArrayList list =new java.util.ArrayList();
private int current =0;
public InorderIterator(){
inorder();
}
private void inorder(){
inorder(root);
}
private void inorder(TreeNode root){
if(root==null)
return;
inorder(root.left);
list.add(root.element);
inorder(root.right);
}
@Override
public boolean hasNext(){
if (current<list.size())
return true;
return false;
}
@Override
public E next(){
return list.get(current++);
}
@Override
public void remove(){
delete(list.get(current));
list.clear();
inorder();
}
}
public void clear(){
root=null;
size=0;
}
public void nonRecursivePreorder(){
java.util.ArrayList<TreeNode> list = new java.util.ArrayList<TreeNode>();
Stack<TreeNode> stack = new Stack<TreeNode>();
if(root==null) return;
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.peek();
stack.pop();
list.add(node);
if(node.right !=null && !list.contains(node.right)){
stack.push(node.right);
}
if(node.left != null && !list.contains(node.left)){
stack.push(node.left);
}
}
for (int i = 0;i< list.size();i++)
System.out.print((list.get(i)).element + " ");
}
}
}
