/**
 * K_CompleteRecBinTree<T> extends K_AbstRecBinTree<T>
 * implementing <code>add</code> and <code>remove</code> methods that
 * preserve the characteristics of a complete binary tree.  A complete
 * binary tree is a binary tree that has 2^k nodes at every level k
 * (in other words, every level is completely filled) except perhaps the
 * deepest level, whose nodes are as far left as possible.
 *
 * INVARIANT: A non-empty K_CompleteRecBinTree tree must always have non-null
 * K_CompleteRecBinTree objects as its left and right children; the children
 * may be empty subtrees.  An empty tree is defined by having null data as
 * well as null left and right children.
 *
 * @author Alyce Brady
 * @version 16 November 2025
 *
 * @param <T> The type of data stored.
 * 
 */
public class K_CompleteRecBinTree<T> extends K_AbstRecBinTree<T>
{
    /** Creates an empty binary tree with no data and no children.
     */
    public K_CompleteRecBinTree()
    {
        super();
    }

    /** {@inheritDoc}
     *  This implementation adds data in breadth-first (top-down,
     *  left-to-right) order, creating a complete binary tree.
     */
    public void add(T value)
    {
        // This implementation adds the data in breadth-first (top-down,
        // left-to-right) order, creating a complete binary tree.

        // Create a queue to use for a breadth-first traversal.
        K_Queue<K_AbstRecBinTree<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_AbstRecBinTree<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}
     *  The node being removed is replaced with the last node in the tree
     *  (the right-most node in the lowest level).  The original
     *  breadth-first traversal order is not preserved, but the tree is
     *  still a complete binary tree (the invariant is preserved).
     */
    public T remove(T itemToFind)
    {
        // If tree is empty, there is nothing to remove.
        if ( isEmpty() )
        {
            return null;
        }

        // Initialize the itemToReturn to be null.
        T itemToReturn = null;

        // Create a queue to use for a breadth-first traversal.
        // This queue will only hold non-empty tree nodes.
        K_Queue<K_AbstRecBinTree<T>> queue = new K_LLQueue<>();

        // Put the root node on the queue, then traverse the tree.
        queue.enqueue(this);
        while( ! queue.isEmpty() )
        {
            K_AbstRecBinTree<T> node = queue.dequeue();

            // Add children to queue for further traversal, but only if not
            // empty. In a complete tree, if the left child is empty, the
            // right child is also.
            if ( ! node.left.isEmpty() )
            {
                queue.enqueue(node.left);
                if ( ! node.right.isEmpty() )
                    queue.enqueue(node.right);
            }

            // Is this node the one to remove?
            if ( node.data.equals(itemToFind) )
            {
                itemToReturn = node.data;

                // Was this the last non-empty node in the tree?
                if ( queue.isEmpty() )
                {
                    // Yes.  Make this node an empty tree.
                    node.data = null;
                    node.left = node.right = null;
                }
                else    // No.  Replace it with the last node.
                {
                    node.data = removeLast(queue);
                }
                return itemToReturn;
            }
        }

        // Item was not found.
        return null;
    }

    /** Removes the last node in the Complete tree (the last leaf
     *  node in a breadth-first traversal).
     *  Pre-condition: The queue is not empty.
     *    @param queue  A non-empty queue containing non-empty nodes that
     *                  still need to be visited.
     *    @return The removed last item.
     */
    private T removeLast(K_Queue<K_AbstRecBinTree<T>> queue)
    {
        K_AbstRecBinTree<T> node;
        T itemToReturn = null;

        // Continue traversing the tree until we get to the last node.
        do
        {
            node = queue.dequeue();

            // Add non-empty children to queue to keep traversing tree.
            if ( ! node.left.isEmpty() )
                queue.enqueue(node.left);
            if ( ! node.right.isEmpty() )
                queue.enqueue(node.right);
        } while( ! queue.isEmpty() );

        // We have reached the last non-empty node; make it an empty tree
        // and return the data that was in it.
        itemToReturn = node.data;
        node.data = null;
        node.left = node.right = null;
        return itemToReturn;
    }

}    //end class K_CompleteRecBinTree<T>