import java.util.List;


public class InternalNode implements Node {
  protected int key;
  protected Node left,right;

  public InternalNode(int key, Node left, Node right) {
    this.key = key;
    this.left = left;
    this.right = right;
  }

  public int getKey() {
    return key;
  }

  public void setKey(int key) {
    this.key = key;
  }

  public Node getLeft() {
    return left;
  }

  public void setLeft(Node left) {
    this.left = left;
  }

  public Node getRight() {
    return right;
  }

  public void setRight(Node right) {
    this.right = right;
  }

  public Node add(int key){
    if (key < this.key) {
      setLeft(getLeft().add(key));
    } else {
      if (key > this.key){
        setRight(getRight().add(key));
      }
    }
    return this;
  }
  @Override public String toString(){
    return getLeft().toString()+" "+getKey()+" "+getRight().toString();
  }

  public Pair<Node> cut(int key){
    Node n1 =null,n2 =null;
    if (getKey()==key){
      n1 = getLeft();
      n2 = getRight();
    } else {
      if (key < getKey()){
        Pair<Node> cutLeft = getLeft().cut(key);
        n1 = cutLeft.getFirst();
        setLeft(cutLeft.getSecond());
        n2= this;
      } else {   
        if (key > getKey()){
          Pair<Node> cutRight = getRight().cut(key);
          n2 = cutRight.getSecond();
          setRight(cutRight.getFirst());
          n1=this;
        }
      }
    }
    return new Pair<Node>(n1,n2);
  }
  // sans se soucier de la complexité
  public List<Integer> toList(){
    List <Integer> l = getLeft().toList();
    l.add(getKey());
    l.addAll(getRight().toList());
    return l;
  }
}