import java.lang.UnsupportedOperationException;

/**
 *  K_RecBinaryTree<T> implements a 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).
 *
 *  This version of a binary tree does not support a remove method,
 *  throwing an exception if the remove method is called.  Subclasses may
 *  override this to support a remove operation.  Since the add method in
 *  this class adds elements in breadth-first order, and since it does not
 *  support the remove method, instances of this class are complete binary
 *  trees.  Instances of subclasses that support a remove method might not
 *  be, though, depending on the behavior of the remove method.
 *
 * @author Autumn C. Spaulding
 * @version 10 December 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: Fall 2025
 *     Modifications Made: Modified to use generics and the K_Queue interface.
 * 
 * Student Modifications:
 *     Modifier: studentName
 *     Modification Date: currentDate
 *     Modifications Made:  Implemented ...
 * 
 */
public class K_RecBinaryTree<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_RecBinaryTree<T> left;
    protected K_RecBinaryTree<T> right;

    /** Creates an empty binary tree with no data and no children.
     */
    public K_RecBinaryTree()
    {
        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_RecBinaryTree<T> leftChild()
    {
        return left;
    }

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

    /** {@inheritDoc}
     *  This implementation adds data in breadth-first (top-down,
     *  left-to-right) order.
     */
    public void add(T value)
    {
        // Create a queue to use for a breadth-first traversal.
        K_Queue<K_RecBinaryTree<T>> queue = new K_LLQueue<>();

        // Put this tree (the root) on the queue, then traverse the tree
        // until we encounter the first empty tree (the root, or an empty
        // tree below a leaf).
        queue.enqueue(this);
        while( ! queue.isEmpty() )
        {
            K_RecBinaryTree<T> tree = queue.dequeue();

            if ( tree.isEmpty() )
            {
                // Turn this empty tree into a leaf node.
                tree.data = value;
                tree.left = new K_CompleteRecBinTree<>();
                tree.right = new K_CompleteRecBinTree<>();
                return;
            }

            // Not empty, so add both children to the queue.
            queue.enqueue(tree.left);
            queue.enqueue(tree.right);
        }

        // Should never get here because any tree is either empty or has
        // empty trees below its leaf nodes.
        return;
    }

    /** {@inheritDoc}
     *  Not supported.
     *  throws UnsupportedOperationException
     */
    public T remove(T itemToFind)
    {
        throw new UnsupportedOperationException("The remove method is not supported.");
    }

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

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

    /** {@inheritDoc}
     */
    public void postOrderTraversal(NodeVisitor<T> visitor)
    {
        // Handle the base case.
        if ( isEmpty() )
            return;

        // Continue with the traversal.
        left.preOrderTraversal(visitor);
        right.preOrderTraversal(visitor);
        visitor.visit(data);
    }    

    /** {@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;
    }

    /** Returns true if this is a leaf; false otherwise.
     *    @return True if this is a leaf; False otherwise.
     */
    public boolean isLeaf()
    {
        if ( ! isEmpty() && ( left.isEmpty() && right.isEmpty() ) )
            return true;

        return false;
    }

}    // end class K_RecBinaryTree<T>