class BiTree {
    private ANode _rootNode;

    public BiTree () {
        _rootNode = EmptyNode.Singleton;
    }

    public Object getRootDat() {
        return _rootNode.getRootDat (this);
    }

    public void setRootDat(Object dat) {
        _rootNode.setRootDat (dat, this);
    }

    public BiTree getLeftSubTree() {
        return _rootNode.getLeftSubTree (this);
    }

    public BiTree getRightSubTree() {
        return _rootNode.getRightSubTree (this);
    }

    public void setLeftSubTree(BiTree biTree) {
        _rootNode.setLeftSubTree(biTree, this);
    }

    public void setRightSubTree(BiTree biTree) {
        _rootNode.setRightSubTree(biTree, this);
    }

    public void insertRoot(Object dat) {
        _rootNode.insertRoot(dat, this);
    }

    public Object remRoot() {
        return _rootNode.remRoot(this);
    }

    public Object execute(IVisitor algo, Object input) {
        return _rootNode.execute(algo, input, this);
    }

    public String toString () {
        return (String)execute (ToString.Singleton, null);
    }

    final void setRootNode(ANode node) {
        _rootNode = node;
    }

    final ANode getRootNode() {
        return _rootNode;
    }

    final Object remParent(BiTree sis, BiTree dad) {
        return _rootNode.remParent (sis, dad, this);
    }

    final Object remParentNode (BiTree dad) {
        return _rootNode.remParentNode (dad, this);
    }
}

abstract class ANode {
    abstract Object getRootDat(BiTree owner);
    abstract void setRootDat(Object dat, BiTree owner);
    abstract BiTree getLeftSubTree(BiTree owner);
    abstract BiTree getRightSubTree(BiTree owner);
    abstract void setLeftSubTree(BiTree biTree, BiTree owner);
    abstract void setRightSubTree(BiTree biTree, BiTree owner);
    abstract void insertRoot(Object dat, BiTree owner);
    abstract Object remRoot(BiTree owner);
    abstract Object remParent(BiTree oSib, BiTree oDad, BiTree owner);
    abstract Object remParentNode (BiTree ownerDad, BiTree owner);
    abstract Object execute(IVisitor algo, Object input, BiTree owner);
}

class EmptyNode extends ANode {
    final static EmptyNode Singleton = new EmptyNode ();

    private EmptyNode (){
    }

    Object getRootDat (BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.getRootDat ()");
    }

    void setRootDat (Object dat, BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.setRootDat ()");
    }

    BiTree getLeftSubTree (BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.getLeftSubTree ()");
    }

    BiTree getRightSubTree(BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.getRightSubTree ()");
    }

    void setLeftSubTree(BiTree biTree, BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.setLeftSubTree ()");
    }

    void setRightSubTree(BiTree biTree, BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.setRightSubTree ()");
    }

    void insertRoot(Object dat, BiTree owner) {
        owner.setRootNode (new DatNode (dat));
    }

    Object remRoot (BiTree owner) {
        throw new java.util.NoSuchElementException ("EmptyNode.remRoot ()");
    }

    Object remParent(BiTree oSib, BiTree oDad, BiTree owner) {
        return oSib.remParentNode (oDad);
    }
    Object remParentNode (BiTree ownerDad, BiTree owner) {
        Object dat = ownerDad.getRootDat();
        ownerDad.setRootNode (EmptyNode.Singleton);
        return dat;
    }

    Object execute(IVisitor algo, Object input, BiTree owner) {
        return algo.emptyCase(owner, input);
    }
}

class DatNode extends ANode {
    private BiTree _leftTree = new BiTree ();
    private Object _dat;
    private BiTree _rightTree = new BiTree ();
    DatNode(Object dat) {
        _dat = dat;
    }
    Object getRootDat(BiTree owner) {
        return _dat;
    }

    void setRootDat(Object dat, BiTree owner) {
        _dat = dat;
    }

    BiTree getLeftSubTree(BiTree owner) {
        return _leftTree;
    }

    BiTree getRightSubTree(BiTree owner) {
        return _rightTree;
    }

    void setLeftSubTree(BiTree biTree, BiTree owner)  {
        _leftTree = biTree;
    }

    void setRightSubTree(BiTree biTree, BiTree owner) {
        _rightTree = biTree;
    }

    void insertRoot(Object dat, BiTree owner) {
        throw new IllegalStateException ("DatNode.insertRoot - Tree is not empty.");
    }

    Object remRoot(BiTree owner) {
        return _leftTree.remParent (_rightTree, owner);
    }

    Object remParent(BiTree oSib, BiTree oDad, BiTree owner) {
        throw new IllegalStateException ("Tree has more than one element.");
    }
    Object remParentNode (BiTree ownerDad, BiTree owner) {
        throw new IllegalStateException ("Tree has more than one element.");
    }

    Object execute(IVisitor algo, Object input, BiTree owner) {
        return algo.nonEmptyCase (owner, input);
    }
}

interface IVisitor {
    public Object emptyCase(BiTree host, Object input);
    public Object nonEmptyCase(BiTree host, Object input);
}

class ToString implements IVisitor {
    public final static ToString Singleton = new ToString ();
    private ToString () {
    }

    public Object emptyCase(BiTree host, Object input) {
        return "[]";
    }

    public Object nonEmptyCase(BiTree host, Object input) {
        String ls
        = (String) host.getLeftSubTree().execute(ToStringHelp.Singleton, "|  ");
        String rs
        = (String)host.getRightSubTree().execute(ToStringHelp.Singleton, "   ");
        return (host.getRootDat() + "\n" + ls + "\n" + rs);
    }
}

class ToStringHelp implements IVisitor {
    public static final ToStringHelp Singleton = new ToStringHelp ();
    private ToStringHelp () {
    }
    public Object emptyCase(BiTree host, Object input) {
        return "|_ []";
    }

    public Object nonEmptyCase(BiTree host, Object leftLead) {
        String ls
            = (String)host.getLeftSubTree().execute(this, leftLead + "|  ");
        String rs
            = (String)host.getRightSubTree().execute(this, leftLead + "   ");
        return ("|_ " + host.getRootDat()+ "\n" +
                leftLead + ls + "\n" +
                leftLead + rs);
    }
}