import java.applet.*;
import java.awt.*;
import java.io.*;
 

//***********************  Applet **********************************************

public class TreeApplet extends Applet {
Abs_tree tree;
boolean is_new_tree=true;
TextField input_elem ;
String nodeValue;
Panel inputPanel;
OutputPanel outputPanel;
Button clear;
int last_x, last_y;

public void init() {
        setBackground(Color.white);
        Label input_elem_label;
        Panel input1;

        //***set layout of applet to borderlayout
        setLayout(new BorderLayout());

        //***create input panel to take input from user.
        inputPanel = new Panel();
        inputPanel.setLayout(new BorderLayout());

        input1 = new Panel();
        input_elem_label = new Label("   Input value of integer:");
        input1.add(input_elem_label);
        input_elem = new TextField(10);
        input1.add(input_elem);

        clear = new Button("Reset");
        input1.add(clear);

        inputPanel.add("North", input1);

        add("North", inputPanel);

        //***create panel to draw the tree (output).
        outputPanel = new OutputPanel();
        add("Center", outputPanel);
        }

//***Actions to perform when the user presses keys

public boolean action(Event e, Object what) {
  //***Clear the output to start on a new tree
  if (e.target.equals(clear))
        { is_new_tree = true;
          input_elem.setText("");
          outputPanel.clearPanel();
        }
  //***On pressing return on input field...
  if (e.target.equals(input_elem))
        { String s = (String)what;

          //***call insert/new with correct element type
           try {
                if (is_new_tree)
                   {
                         tree=new Tree(new IntElem(Integer.parseInt(s)));
                    is_new_tree = false;
                   } //***end of if is_new_tree
                else {
                         tree.insert(new IntElem(Integer.parseInt(s)));
                     }
                } //***end of try

           catch(Exception exception)
                { showStatus("Cannot insert this type");
                  input_elem.selectAll();
                  return true;
                }

           outputPanel.drawTree(tree);
           input_elem.selectAll();
           return true;
        } //***end of if target.equals(input_elem)

   return true;
   } //***end of method action
} //***end of class

//***The output area, where the tree is drawn
class OutputPanel extends Panel {
Image treeImage;    //***buffer to keep the latest tree representation
int imageWidth, imageHeight;

public void paint(Graphics g) {
 if (treeImage == null)
 { Dimension d = size(); //***Initialize image buffer
   treeImage = createImage(d.width, d.height);
   imageWidth = d.width; imageHeight = d.width;
   Graphics gr = treeImage.getGraphics();
   gr.setColor(getBackground());
   gr.fillRect(0, 0, imageWidth, imageHeight);
 }
 g.drawImage(treeImage, 0, 0, this);
 }

public void clearPanel() {
 Graphics g;
 //***Clear the image
 g = treeImage.getGraphics();
 g.setColor(getBackground());
 g.fillRect(0, 0, imageWidth, imageHeight);
 getGraphics().drawImage(treeImage, 0, 0, this);
 }

//***draw the tree on the output panel
public void drawTree(Abs_tree tree) {
 Graphics g;
 Dimension d = size();
 if (imageWidth != d.width || imageHeight != d.height)
    { treeImage = createImage(d.width, d.height);
      imageWidth = d.width; imageHeight = d.height;
    };
 //***Clear the image
 g = treeImage.getGraphics();
 g.setColor(getBackground());
 g.fillRect(0, 0, d.width, d.height);
 drawNode(g, imageWidth/2, tree, imageWidth/2, 10);
 getGraphics().drawImage(treeImage, 0, 0, this);
 }
 //***private method to draw a note
 private void drawNode(Graphics g, int subtreeW, Abs_tree tree, int x, int y) {
 if(tree==null) return;
 g.setColor(Color.blue);
 g.drawString(tree.get_result(),x,y);
 if(tree.left !=null){
 g.setColor(Color.red);
g.drawLine(x+6,y+4,x-subtreeW/2+8,y+42);
}
 drawNode(g, subtreeW/2,tree.left,x-subtreeW/2,y+55);
 if(tree.right !=null){
 g.setColor(Color.red);
g.drawLine(x+9,y+4,x+subtreeW/2+8,y+42);
}
 drawNode(g, subtreeW/2,tree.right,x+subtreeW/2,y+55);
  }
}

//***************************** Interface Element **********************************

interface Element{
 public boolean equal(Element e);
 public boolean lessThan(Element e);
 public String get_value();
}

//****************** IntElem and StringElem ****************************************

class IntElem implements Element{
  //***data
  private int x;
  //***constructors
  public IntElem(int x){this.x=x;}
  public IntElem(){super();}
  public IntElem(Element x){this.x=Integer.parseInt(x.get_value());}
  //***method functions
  public String get_value(){return Integer.toString(this.x);}
  public boolean equal(Element e){return this.x==Integer.parseInt(e.get_value());}
  public boolean lessThan(Element e){return this.x<Integer.parseInt(e.get_value());}
}

class StringElem implements Element{
  //***data
  private String s;
  //***constructors
  public StringElem(String s){this.s=s;}
  public StringElem(){super();}
  public StringElem(Element s){this.s=s.get_value();}
  //***method functions
  public String get_value(){return this.s;}
  public boolean equal(Element s){return this.s.equals(s.get_value());}
  public boolean lessThan(Element s){
    return this.s.compareTo(s.get_value())<0;}
}

//************************  Tree **************************************************

abstract class Abs_tree {
 public Abs_tree(Element n) { value = n; left = null; right = null;};
 public void insert(Element n) {
      if (value.equal(n)) count_duplicates();
      else if (value.lessThan(n))
                if (right == null) right = add_node(n);
                else right.insert(n);
      else if (left == null) left = add_node(n);
              else left.insert(n);
        }

 public void print()   {
        if (left != null) left.print();
        this.print_node();
        if (right != null) right.print();
        }

 protected Element value;
 protected Abs_tree left;
 protected Abs_tree right;

 protected abstract void count_duplicates();
 protected abstract Abs_tree add_node(Element n);
 protected abstract void print_node();
 protected abstract String get_result();
}

//**************************  Tree   ************************************************

class Tree extends Abs_tree {
 public Tree(Element n) {super(n);}
 protected Abs_tree add_node(Element n) {return new Tree(n);}
 protected void count_duplicates() {}
 protected String get_result() {return value.get_value();}
 protected void print_node() {System.out.print(value.get_value() + "  ");}
}

//************************  Duptree *************************************************

class Duptree extends Abs_tree {
 public Duptree(Element n) {super(n); count = 1;};
 protected Abs_tree add_node(Element n) {return new Duptree(n);}
 protected void count_duplicates() {count++;}
 protected void print_node() {
   System.out.print(value.get_value() + "/" + count + "  ");}
 protected String  get_result(){return value.get_value() +"/"+ count+ " ";}
 protected int count;
}

// *******************************End of Program *********************************