type BinaryStringTree = {
    setLeft(_:BinaryStringTree)->Void
    setRight(_:BinaryStringTree)->Void
    clear->Void
    isEmpty->Boolean
    isLeaf->Boolean
    isLeftChild->Boolean
    isRightChild->Boolean
    isRoot->Boolean
    height->Number
    depth->Number
    getString->String
    getLeftChild->BinaryStringTree
    getRightChild->BinaryStringTree
    getParent->BinaryStringTree
    getRoot->BinaryStringTree
    setParent(_:BinaryStringTree)->Void
    ==(_:BinaryStringTree)->Boolean}

// Constructs empty tree
// @post @return empty node
method new->BinaryStringTree is public{EmptyTree}


//Constructs tree with no children 
// @post @return tree with value str and 2 empty subtrees
// @param str: a non-empty string

method withValue(str:String)->BinaryStringTree is public{
     var tr:BinaryStringTree := BinaryTree.new(str, EmptyTree, EmptyTree)
     tr.setLeft(EmptyTree)
     tr.setRight(EmptyTree)
     return tr}


//Constructs tree with two children
// @post @return tree with value str and two subtrees
// @param str: a non-empty string
// @param lt, rt: left and right subtrees

method withValue(str:String)left(lt:BinaryStringTree)
    right(rt:BinaryStringTree)->BinaryStringTree is public{
        var tr:BinaryStringTree := BinaryTree.new(str, lt, rt)
        tr.setLeft(lt)
        tr.setRight(rt)
        return tr}


// Instance of empty tree
def EmptyTree:BinaryStringTree is public, readable = object{

    var value:String is readable:= ""

    var parent:BinaryStringTree is readable := self

    var left:BinaryStringTree is readable := self

    var right:BinaryStringTree is readable := self

    method setLeft(_:BinaryStringTree)->Void is public{
        print "can't set left of empty tree"}

    method setRight(_:BinaryStringTree)->Void is public{
        print "can't set right of empty tree"}

    method clear->Void is public{return Void}

    method isEmpty->Boolean is public{true}

    method isLeaf->Boolean is public{false}

    method isLeftChild->Boolean is public{false}

    method isRightChild->Boolean is public{false}

    method isRoot->Boolean is public{false}

    method height->Number is public{-1}

    method depth->Number is public{0}

    method getString->String is public{value}

    method getLeftChild->BinaryStringTree is public{left}

    method getRightChild->BinaryStringTree is public{right}

    method getParent->BinaryStringTree is public{parent}

    method getRoot->BinaryStringTree is public{self}

    method setParent(_:BinaryStringTree)->Void is public{return Void}

    method ==(bt:BinaryStringTree)->Boolean is public{bt.isEmpty}
}

class BinaryTree.new(str:String, lt:BinaryStringTree, rt:BinaryStringTree){

    var value:String is readable := str

    var parent:BinaryStringTree is readable := EmptyTree

    var left:BinaryStringTree is readable := EmptyTree

    var right:BinaryStringTree is readable := EmptyTree

    // @post sets left subtree to newLeft, reparents newLeft if not empty
    // @param newLeft the root of the new left subtree
    method setLeft(newLeft:BinaryStringTree)->Void is public{
        left := newLeft
        if(!newLeft.isEmpty) then {left.setParent(self)}
    }

    // @post sets right subtree to newRight, reparents newRight if not empty
    // @param newRight the root of the new right subtree
    method setRight(newRight:BinaryStringTree)->Void is public{
        right := newRight
        if(!newRight.isEmpty) then {right.setParent(self)}
    }

    // @post replaces tree with an empty one
    method clear->Void is public{
        if(isLeftChild) then{parent.setLeft(EmptyTree)}
        else{if(isRightChild) then{parent.setRight(EmptyTree)}}
        value := ""
        left := EmptyTree
        right := EmptyTree
        parent := EmptyTree}

    // @post @return true iff node is empty
    method isEmpty->Boolean is public{false}

    // @post @return true iff node is a leaf (has parent but no children)
    method isLeaf->Boolean is public{!parent.isEmpty && left.isEmpty && right.isEmpty}

    // @post @return true iff node is a left child
    method isLeftChild->Boolean is public{!parent.isEmpty && (self == parent.getLeftChild)}

    // @post @return true iff node is a right child
    method isRightChild->Boolean is public{!parent.isEmpty && (self == parent.getRightChild)}

    // @post @return true iff node is root of tree
    method isRoot->Boolean is public{!isEmpty && parent.isEmpty}

    // @post @return maximum path length from this node to a leaf
    method height->Number is public{
        var max:Number := 
             if(left.height > right.height) then{left.height}
             else{right.height}
        return 1 + max}

    // @post @return path length from this node to root
    method depth->Number is public{
        if(parent.isEmpty) then {0}
        else{1 + parent.depth}
    }

    // @post @return string value of node
    method getString->String is public{value}

    // @post @return left child of node
    method getLeftChild->BinaryStringTree is public{left}

    // @post @return right child of node
    method getRightChild->BinaryStringTree is public{right}

    // @post @return parent of node
    method getParent->BinaryStringTree is public{parent}

    // @post @return the root of the tree
    method getRoot->BinaryStringTree is public{
        var finger:BinaryStringTree := self
        while{!finger.isRoot} do {finger := finger.getParent}
        return finger}

    // @post reparents node to parent reference
    // @param newParent a reference to the new parent of this node
    method setParent(newParent:BinaryStringTree)->Void is public{
       parent := newParent}

    // @post @return true iff the two trees have same value and subtrees
    method ==(bt:BinaryStringTree)->Boolean is public{
        (value == bt.getString) && (left == bt.getLeftChild) && (right == bt.getRightChild)}
}