/*
 * BinarySearchTree.kt
 * 
 * Based on Dave Musicant's BinarySearchTree.kt from Fall 2024,
 * which was ported by Dave from the BST code at
 * https://www.programiz.com/dsa/binary-search-tree.
 * 
 * Modified by Tanya Amert for Spring 2025.
 * 
 * Illustrates an implementation of a BST.
 */

class BinarySearchTree {

    // This is sort of like a hierarchical linked list :)
    private data class Node(var key: Int,
                            var left: Node? = null,
                            var right: Node? = null)

    // Nobody needs to know about the root of our tree
    private var root: Node? = null

    // Inserts a key into the binary search tree
    fun insert(key: Int) {
        root = insertKey(root, key)
    }

    // We'll traverse recursively until we find the right spot,
    // so this is like a recursive helper function (called initially
    // with the root of the tree)
    private fun insertKey(root: Node?, key: Int): Node? {
        // Return a new node if the tree is empty
        if (root == null) {
            return Node(key)
        }

        // Traverse to the right place and insert the node
        if (key < root.key) {
            root.left = insertKey(root.left, key)
        } else if (key > root.key) {
            root.right = insertKey(root.right, key)
        }

        return root
    }

    // Perform an in-order tree traversal, printing as we go
    fun inorder() {
        inorderRec(root)
    }

    // We'll actually do this recursively, again starting at the root
    private fun inorderRec(root: Node?) {
        if (root != null) {
            inorderRec(root.left)
            print("${root.key} -> ")
            inorderRec(root.right)
        }
    }

    // Deletes a key from the binary search tree
    fun deleteKey(key: Int) {
        root = deleteRec(root, key)
    }

    // We'll traverse recursively until we find the key to delete,
    // so this is like a recursive helper function (called initially
    // with the root of the tree)
    private fun deleteRec(root: Node?, key: Int): Node? {
        // Return if the tree is empty
        if (root == null)
            return root

        // Find the node to be deleted
        if (key < root.key) {
            root.left = deleteRec(root.left, key)
        } else if (key > root.key) {
            root.right = deleteRec(root.right, key)
        } else {
            // We found the node to delete!  It's easy if it has one
            // or no children...
            if (root.left == null)
                return root.right
            else if (root.right == null)
                return root.left

            // If the node has two children, place the in-order successor
            // in the position of the node to be deleted
            root.key = minValue(root.right!!)

            // Delete the in-order successor
            root.right = deleteRec(root.right, root.key)
        }

        return root
    }

    // Find the inorder successor (used in key deletion)
    private fun minValue(root: Node): Int {
        var current = root
        var minv = current.key
        while (current.left != null) {
            minv = current.left!!.key
            current = current.left!!
        }
        return minv
    }
}

// Driver Program to test the above functions
fun main() {
    val tree = BinarySearchTree()

    tree.insert(8)
    tree.insert(3)
    tree.insert(1)
    tree.insert(6)
    tree.insert(7)
    tree.insert(10)
    tree.insert(14)
    tree.insert(4)

    print("Inorder traversal: ")
    tree.inorder()

    println("\n\nAfter deleting 10")
    tree.deleteKey(10)
    print("Inorder traversal: ")
    tree.inorder()
}