public class Node<Element>
{
    /**
     * A node storing element element, has references to the parent node, 
     * and the left and right children (null if not present)
     */
    private Element element;
    private Node<Element> left, right, parent;
    
    /**
     * Constructor creating a new node containing element k
     */
    public Node(Element k) {
        left = right = parent = null;
        element = k;
    }
    
    // Accessor methods
    public Node<Element> getLeft() { return left; }
    public Node<Element> getRight() { return right; }
    public Node<Element> getParent() { return parent; }
    public Element getElement() { return element; }

    /**
     * Update element of node to element k
     */
    public void setElement(Element k) {
        element = k;        
    }

    /**
     * Change the reference to the left child; also updates the parent reference of
     * the new left child to point to this node; the old left node's parent is set to null
     */
    public void setLeft(Node<Element> new_left) {
        if (left != null) left.parent = null;
        left = new_left;
        if (left != null) left.parent = this;
    }

    /**
     * Change the reference to the right child; also updates the parent reference of
     * the new right child to point to this node; the old right node's parent is set to null
     */
    public void setRight(Node<Element> new_right) {
        if (right != null) right.parent = null;
        right = new_right;
        if (right != null) right.parent = this;
    }    
}