/**
 * K_AbstRecBinTree<T> implements an abstract binary tree structure
 * as a recursive data structure, with the class acting as the node
 * (implicit node structure). The recursive tree definition used in this
 * class is as follows.
 *     A binary tree is either:
 *        1.  An empty tree; or
 *        2.  A node, called a root, containing data and two children, left
 *            and right, each of which is itself a binary tree.
 *
 *  In this implementation, an empty tree is represented by a node with null
 *  data and null references for the children.  A leaf node is represented by
 *  a node with a data value and two references to empty trees (NOT a data
 *  value and two null references).  We could represent this as an object
 *  invariant: data, left, right are either all null (representing an empty
 *  tree) or none of them are null (a non-empty tree).
 * 
 * @author Autumn C. Spaulding
 * @version 16 November 2025
 *
 * @param <T> The type of data stored.
 * 
 * Creation Date: 24 July 2000
 * Modifications:
 *     Modifier: Alyce Brady
 *     Modification Date: November 11, 2002
 *     Modifications Made: Modifications to documentation (e.g., to remove
 *         empty preconditions); added levelOrderTraversal;
 *         also modified to use NodeVisitor interface.
 * 
 *     Modifier: Nathan Sprague
 *     Modification Date: May 10, 2010
 *     Modifications Made: Modified to use Java Queue interface.
 * 
 *     Modifier: Alyce Brady
 *     Modification Date: October 27, 2025
 *     Modifications Made: Modified to use generics and the K_Queue interface.
 *     Modification Date: November 16, 2025
 *     Modifications Made: Modified to be abstract and fine-tune generics.
 * 
 * Student Modifications:
 *     Modifier: studentName
 *     Modification Date: currentDate
 *     Modifications Made:  Implemented ...
 * 
 */

public abstract class K_AbstRecBinTree<T> implements K_BinaryTree<T>
{
    // Instance variables are protected, not private, so they can be used
    // by subclasses, if appropriate.
    protected T data; 
    protected K_AbstRecBinTree<T> left;
    protected K_AbstRecBinTree<T> right;

    /** Creates an empty binary tree with no data and no children.
     */
    public K_AbstRecBinTree()
    {
        data = null;
        left = null;
        right = null;
    }

    /** {@inheritDoc}
     */
    public boolean isEmpty()
    {
        return data == null;
    }

    /** Gets the data associated with the root node of this particular tree
     *  or null if the tree is empty.
     *      @return The value associated with tree's root node; 
     *                    or null if tree is empty.
     */
    public T getData()
    {
        return data;
    }

    /** Gets the left child of the current tree.
     *      @return The left child (a tree).
     */
    public K_AbstRecBinTree<T> leftChild()
    {
        return left;
    }

    /** Gets the right child of the current tree.
     *      @return The right child (a tree).
     */
    public K_AbstRecBinTree<T> rightChild()
    {
        return right;
    }

    /** {@inheritDoc}
     */
    public abstract void add(T value);

    /** {@inheritDoc}
     */
    public abstract T remove(T itemToFind);

    /** {@inheritDoc}
     */
    public void preOrderTraversal(NodeVisitor<T> visitor)
    {
        if ( isEmpty() )
            return;
        visitor.visit(data);
        left.preOrderTraversal(visitor);
        right.preOrderTraversal(visitor);
    }    

    /** {@inheritDoc}
     */
    public void inOrderTraversal(NodeVisitor<T> visitor)
    {
        // NEED CODE HERE !!!
    }    

    /** {@inheritDoc}
     */
    public void postOrderTraversal(NodeVisitor<T> visitor)
    {
        // NEED CODE HERE !!!
    }    

    /** {@inheritDoc}
     */
    public void breadthFirstTraversal(NodeVisitor<T> visitor)
    {
        // NEED CODE HERE !!!
    }    

    /** {@inheritDoc}
     */
    public int height()
    {
        if ( isEmpty() )
            return 0;

        // The height of this tree is 1 more than the height of the
        // "taller" child.
        int leftHeight = leftChild().height();
        int rightHeight = rightChild().height();
        if ( leftHeight >= rightHeight )
            return leftHeight + 1;
        else
            return rightHeight + 1;
    }

}    //end class K_AbstRecBinTree<T>