import java.util.*;

public class Node {
    private String element;
    private Node left;
    private Node right;
    private Node parent;
	
    /**Creates a node with null references to its element and next node */
    public Node(){
	this("",null,null,null);
    }
	
    /** Creates a node with the given element, left, right, and parent*/
    public Node(String e, Node left,Node right,Node parent){
	this.element = e;
	this.left    = left;
	this.right   = right;
	this.parent  = parent;
    }

    public String element(){return element;}
    public Node left(){return left;}
    public Node right(){return right;}
    public Node parent(){return parent;}

    public void setElement(String s){this.element = s;}
    public boolean setLeft(Node x){this.left = x; if (x != null) x.setParent(this); return true;}
    public boolean setRight(Node x){this.right = x; if (x != null) x.setParent(this); return true;}
    public void setParent(Node x){this.parent = x;}

    private int degree(){
	int degree = 0;
	if (left != null) degree++;
	if (right != null) degree++;
	return degree;
    }

    public boolean isRoot(){return parent == null;}
    public boolean isLeaf(){return degree() == 0;}
    public boolean isInternal(){return degree() == 2;}
    public boolean isLeftChild(){return parent.left() == this;}
    public boolean isRightChild(){return parent.right() == this;}
    public boolean hasLeft(){return left != null;}
    public boolean hasRight(){return right != null;}

    private Node getMin(){
	Node x = this;
	while (x.left() != null) x = x.left();
	return x;
    }
    //
    // deliver the node with smallest element in the subtree rooted on this
    //

    private void deleteNotInternal(){
	Node v = parent();
	if (isRightChild() && left() == null) v.setRight(right());
	else if (isRightChild() && right() == null) v.setRight(left());
	else if (isLeftChild() && left() == null) v.setLeft(right());
	else if (isLeftChild() && right() == null) v.setLeft(left());
    }

    public void delete(){
	if (isInternal()){
	    Node y = right().getMin();
	    setElement(y.element());
	    y.deleteNotInternal();
	}
	else deleteNotInternal();
    }
    

    public boolean insert(String s){
    return (s.compareTo(element()) < 0 && hasLeft() && left().insert(s)) ||
	(s.compareTo(element()) > 0 && hasRight() && right().insert(s)) ||
	(s.compareTo(element()) < 0 && !hasLeft() && setLeft(new Node(s,null,null,this))) ||
	(s.compareTo(element()) > 0 && !hasRight() && setRight(new Node(s,null,null,this)));
    }

    public boolean isPresent(String s){
	return (s.compareTo(element()) == 0) ||
	    (s.compareTo(element()) > 0 && hasRight() && right().isPresent(s)) ||
	    (s.compareTo(element()) < 0 && hasLeft() && left().isPresent(s));
    }

    public int height(){
	if (isLeaf()) return 1;
	else if (isInternal()) return 1 + Math.max(left.height(),right.height());
	else if (hasLeft()) return 1 + left.height();
	else return 1 + right.height();
    }
				   

    public Node find(String s){
	if (s.compareTo(element()) == 0) return this;
	else if (s.compareTo(element()) > 0 && hasRight()) return right().find(s);
	else if (s.compareTo(element()) < 0 && hasLeft()) return left().find(s);
	else return null;
    }
    //
    // delivers the node that constains string s
    //

    public void show(){
	System.out.print("(");
	if (hasLeft()) left().show();
	System.out.print("," + element() + ",");
	if (hasRight()) right().show();
	System.out.print(")");
    }
    //
    // an inorder traversal delivering tree in Caley notation
    //

    public String inorder(){
	System.out.print("   inorder("); this.show(); System.out.println(")");
	String s = "";
	if (hasLeft()) s = s + left.inorder();
	System.out.println("     output: "+ element);
	s = s + element;
	if (hasRight()) s = s + right.inorder();
	return s;
    }

    private void draw(double x,double xLow,double xHi,double y,double dY){
	StdDraw.filledCircle(x,y,0.001);
	double xLeft  = (xLow + x)/2.0;
	double xRight = (x + xHi)/2.0;
	if (hasLeft()){
	    StdDraw.line(x,y,xLeft,y+dY);
	    left().draw(xLeft,xLow,x,y+dY,dY);
	}
	if (hasRight()){
	    StdDraw.line(x,y,xRight,y+dY);
	    right().draw(xRight,x,xHi,y+dY,dY);
	}
    }

    public void draw(){
	int h = height();
	double dY = -1.0 / (double)h;
	draw(0.5,0.0,1.0,1.0,dY);
    }
    //
    // rescales y-delta for height
    //
	    
}