///////////////////////////////////////////
///
/// Title: Binary Search Tree
/// Author: Evan Gaul
/// Email: eagaul@wisc.edu
/// Date: 9/10/25
/// Course: CS400 Lec004 Fall 2025
/// Professor: Ashley Samuelson
///
///////////////////////////////////////////

import java.util.LinkedList;
import java.util.Queue;

/**
 * Implementation of a basic binary search tree
 * Implements SortedCollection
 */
public class BinarySearchTree<T extends Comparable<T>> implements SortedCollection<T> {

    protected BinaryNode<T> root;

    /**
     * Initializes an empty BST
     */
    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * Inserts a new value into the BST.
     */
    @Override
    public void insert(T data) throws NullPointerException {
        if (data == null) throw new NullPointerException("Cannot insert null");

        BinaryNode<T> newNode = new BinaryNode<>(data);

        if (root == null) {
            root = newNode;
        } else {
            insertHelper(newNode, root);
        }
    }

    public String levelOrderString() {

        if (root == null) return "";

        StringBuilder sb = new StringBuilder();
        Queue<BinaryNode<T>> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryNode<T> current = queue.poll();
            sb.append(current.getData()).append(" ");

            if (current.getLeft() != null) {
                queue.add(current.getLeft());
            }
            if (current.getRight() != null) {
                queue.add(current.getRight());
            }
        }

        // Remove trailing space
        if (sb.length() > 0) sb.setLength(sb.length() - 1);
        return sb.toString();
    }
    /**
     * Performs the naive binary search tree insert algorithm to recursively
     * insert the provided newNode (which has already been initialized with a
     * data value) into the provided tree/subtree. When the provided subtree
     * is null, this method does nothing.
     */
    protected void insertHelper(BinaryNode<T> newNode, BinaryNode<T> subtree) {
        if (subtree == null || newNode == null) return;

        if (newNode.getData().compareTo(subtree.getData()) <= 0) {
            // Go left
            if (subtree.getLeft() == null) {
                subtree.setLeft(newNode);
                newNode.setParent(subtree);
            } else {
                insertHelper(newNode, subtree.getLeft());
            }
        } else {
            // Go right
            if (subtree.getRight() == null) {
                subtree.setRight(newNode);
                newNode.setParent(subtree);
            } else {
                insertHelper(newNode, subtree.getRight());
            }
        }
    }

    /**
     * Checks if a value exists in a BST
     * @param data the value to check for in the collection
     * @return True if the value exists, false if not
     * @throws NullPointerException, data doesn't exist
     */
    @Override
    public boolean contains(Comparable data) throws NullPointerException {
        if (data == null) throw new NullPointerException("Cant search for null");
        return containsHelper(root, data);
    }

    /**
     * recursive helper method for contains()
     * @param subtree new tree
     * @param data data to find
     * @return True if the value exists, false if not
     */
    private boolean containsHelper(BinaryNode<T> subtree, Comparable<T> data) {
        if (subtree == null) return false; // base case :O
        // Use compareTo to compare the current value against the target, will be 0 if equal
        int cmp = data.compareTo(subtree.getData());
        if (cmp == 0) return true;
        else if (cmp < 0) return containsHelper(subtree.getLeft(), data); // recursive left subtree
        else return containsHelper(subtree.getRight(), data); // recursive in right subtree
    }

    /**
     * Returns number of elements in the BST
     */
    @Override
    public int size() {
        return sizeHelper(root);
    }

    /**
     * Recursive helper method for size()
     * @param subtree - subtree of the BST
     * @return the size of the BST
     */
    private int sizeHelper(BinaryNode<T> subtree) {
        if (subtree == null) return 0;
        // Recursively go through the tree to get the size
        return 1 + sizeHelper(subtree.getLeft()) + sizeHelper(subtree.getRight());
    }

    /**
     * Tells if the BST is empty or not
     * @return true if BST is empty, false if not
     */
    @Override
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Clears the BST (sets root to null)
     */
    @Override
    public void clear() {
        root = null;
    }



    /**
     * ////////////////////////////////////
     *          Test Methods!! :)
     * ////////////////////////////////////
     */


    /**
     * Test insert() and contains()
     * @return true if passed, false if not
     */
    public boolean testSizeContains() {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(2);
        bst.insert(4);
        bst.insert(6);
        bst.insert(8);

        // Test Contains
        if (!bst.contains(5)) return false; // root
        if (!bst.contains(3)) return false;
        if (!bst.contains(8)) return false;
        if (!bst.contains(2)) return false;
        if (bst.contains(10)) return false; // not in tree

        return true;
    }

    /**
     * Test size() and isEmpty()
     * @return true if passed, false if not
     */
    public boolean testSize() {
        try {
            BinarySearchTree<Integer> bst = new BinarySearchTree<>();
            // Add in integer values
            bst.insert(10);
            bst.insert(5);
            bst.insert(15);
            bst.insert(10); // duplicate to left

            if (bst.size() != 4) return false; // test size

            bst.clear();
            if (!bst.isEmpty()) return false;

            return true;
        } catch (Exception e) {
            return false;
        }
    }

    /**
     * Test clear() and isEmpty()
     * @return true if passed, false if not
     */
    public boolean testClearIsEmpty() {
        BinarySearchTree<String> tree = new BinarySearchTree<>();
        tree.insert("a");
        tree.insert("b");
        tree.clear();
        return tree.isEmpty();
    }

    /**
     * Main method to run tests!
     */
    public static void main(String[] args) {
        BinarySearchTree<Integer> intTree = new BinarySearchTree<>();
        System.out.println("Test contains() and size(): " + intTree.testSizeContains());
        System.out.println("Test clear() and isEmpty(): " + intTree.testClearIsEmpty());

        BinarySearchTree<String> stringTree = new BinarySearchTree<>();
        System.out.println("Test size(): " + stringTree.testSize());
    }
}