package trees;

public abstract class BaseNode {
    BaseNode left, right;
    char c;

    abstract boolean add(char c);
    abstract void toString(StringBuilder sb);

    /**
     * Determine the height of the tree.
     */
    int height() {
        int hr = 0, hl = 0;
        if(right != null) hr = right.height();
        if(left != null) hl = left.height();
        if(hr > hl)
            return 1 + hr;
        else
            return 1 + hl;
    }

    /**
     * Determine the number of nodes in the tree.
     * Note how this calculation differs from height.
     */
    int nodeCount() {
        int ncr = 0, ncl = 0;
        if(right != null) ncr = right.nodeCount();
        if(left != null) ncl = left.nodeCount();
        return 1 + ncr + ncl;
    }

    void visit(BinaryTreeVisitor bv) {
        if(left != null) left.visit(bv);
        bv.visit(this);
        if(right != null) right.visit(bv);
    }

    boolean contains(char c) {
        if(this.c == c)
            return true;
        if(c < this.c && left != null && left.contains(c))
            return true;
        if(this.c < c && right != null && right.contains(c))
            return true;
        return false;
    }
}