package com.thealgorithms.datastructures.trees;

import com.thealgorithms.datastructures.trees.BinaryTree.Node;

/**
 *
 *
 * <h1>Binary Search Tree (Iterative)</h1>
 *
 * <p>
 * An implementation of BST iteratively. Binary Search Tree is a binary tree
 * which satisfies three properties: left child is less than root node, right
 * child is grater than root node, both left and right child must themselves be
 * a BST.
 *
 * @author [Lakhan Nad](<a href="https://github.com/Lakhan-Nad">git-Lakhan Nad</a>)
 */

public class BSTIterative {

    /**
     * Reference for the node of BST.
     */
    private Node root;

    /**
     * Default Constructor Initializes the root of BST with null.
     */
    BSTIterative() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * A method to insert a new value in BST. If the given value is already
     * present in BST the insertion is ignored.
     *
     * @param data the value to be inserted
     */
    public void add(int data) {
        Node parent = null;
        Node temp = this.root;
        int rightOrLeft = -1;
        /* Finds the proper place this node can
         * be placed in according to rules of BST.
         */
        while (temp != null) {
            if (temp.data > data) {
                parent = temp;
                temp = parent.left;
                rightOrLeft = 0;
            } else if (temp.data < data) {
                parent = temp;
                temp = parent.right;
                rightOrLeft = 1;
            } else {
                System.out.println(data + " is already present in BST.");
                return; // if data already present we ignore insertion
            }
        }
        /* Creates a newNode with the value passed
         * Since this data doesn't already exists
         */
        Node newNode = new Node(data);
        /* If the parent node is null
         * then the insertion is to be done in
         * root itself.
         */
        if (parent == null) {
            this.root = newNode;
        } else {
            /* Check if insertion is to be made in
             * left or right subtree.
             */
            if (rightOrLeft == 0) {
                parent.left = newNode;
            } else {
                parent.right = newNode;
            }
        }
    }

    /**
     * A method to delete the node in BST. If node is present it will be deleted
     *
     * @param data the value that needs to be deleted
     */
    public void remove(int data) {
        Node parent = null;
        Node temp = this.root;
        int rightOrLeft = -1;
        /* Find the parent of the node and node itself
         * That is to be deleted.
         * parent variable store parent
         * temp stores node itself.
         * rightOrLeft use to keep track weather child
         * is left or right subtree
         */
        while (temp != null) {
            if (temp.data == data) {
                break;
            } else if (temp.data > data) {
                parent = temp;
                temp = parent.left;
                rightOrLeft = 0;
            } else {
                parent = temp;
                temp = parent.right;
                rightOrLeft = 1;
            }
        }
        /* If temp is null than node with given value is not
         * present in our tree.
         */
        if (temp != null) {
            Node replacement; // used to store the new values for replacing nodes
            if (temp.right == null && temp.left == null) { // Leaf node Case
                replacement = null;
            } else if (temp.right == null) { // Node with only right child
                replacement = temp.left;
                temp.left = null;
            } else if (temp.left == null) { // Node with only left child
                replacement = temp.right;
                temp.right = null;
            } else {
                /* If both left and right child are present
                 * we replace this nodes data with
                 * leftmost node's data in its right subtree
                 * to maintain the balance of BST.
                 * And then delete that node
                 */
                if (temp.right.left == null) {
                    temp.data = temp.right.data;
                    replacement = temp;
                    temp.right = temp.right.right;
                } else {
                    Node parent2 = temp.right;
                    Node child = temp.right.left;
                    while (child.left != null) {
                        parent2 = child;
                        child = parent2.left;
                    }
                    temp.data = child.data;
                    parent2.left = child.right;
                    replacement = temp;
                }
            }
            /* Change references of parent after
             * deleting the child.
             */
            if (parent == null) {
                this.root = replacement;
            } else {
                if (rightOrLeft == 0) {
                    parent.left = replacement;
                } else {
                    parent.right = replacement;
                }
            }
        }
    }

    /**
     * A method to check if given data exists in out Binary Search Tree.
     *
     * @param data the value that needs to be searched for
     * @return boolean representing if the value was find
     */
    public boolean find(int data) {
        Node temp = this.root;
        /* Check if node exists
         */
        while (temp != null) {
            if (temp.data > data) {
                temp = temp.left;
            } else if (temp.data < data) {
                temp = temp.right;
            } else {
                /* If found return true
                 */
                System.out.println(data + " is present in the BST.");
                return true;
            }
        }
        System.out.println(data + " not found.");
        return false;
    }
}