/**
 *
 *
 * <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 childs must themselves be a BST.
 *
 * @author [Lakhan Nad](https://github.com/Lakhan-Nad)
 */
import java.util.Stack;

public class BSTIterative {
  /** Reference for the node of BST. */
  private Node root;

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

  /** main function for tests */
  public static void main(String[] args) {
    BSTIterative tree = new BSTIterative();
    tree.add(3);
    tree.add(2);
    tree.add(9);
    assert !tree.find(4) : "4 is not yet present in BST";
    assert tree.find(2) : "2 should be present in BST";
    tree.remove(2);
    assert !tree.find(2) : "2 was just deleted from BST";
    tree.remove(1);
    assert !tree.find(1) : "Since 1 was not present so find deleting would do no change";
    tree.add(30);
    tree.add(40);
    assert tree.find(40) : "40 was inserted but not found";
    /*
       Will print following order
       3 9 30 40
    */
    tree.inorder();
  }

  /**
   * 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 for inorder traversal of BST. */
  public void inorder() {
    if (this.root == null) {
      System.out.println("This BST is empty.");
      return;
    }
    System.out.println("Inorder traversal of this tree is:");
    Stack<Node> st = new Stack<Node>();
    Node cur = this.root;
    while (cur != null || !st.empty()) {
      while (cur != null) {
        st.push(cur);
        cur = cur.left;
      }
      cur = st.pop();
      System.out.print(cur.data + " ");
      cur = cur.right;
    }
    System.out.println(); // for next line
  }

  /** A method used to print postorder traversal of BST. */
  public void postorder() {
    if (this.root == null) {
      System.out.println("This BST is empty.");
      return;
    }
    System.out.println("Postorder traversal of this tree is:");
    Stack<Node> st = new Stack<Node>();
    Node cur = this.root, temp2;
    while (cur != null || !st.empty()) {
      if (cur != null) {
        st.push(cur);
        cur = cur.left;
      } else {
        temp2 = st.peek();
        if (temp2.right != null) {
          cur = temp2.right;
        } else {
          st.pop();
          while (!st.empty() && st.peek().right == temp2) {
            System.out.print(temp2.data + " ");
            temp2 = st.pop();
          }
          System.out.print(temp2.data + " ");
        }
      }
    }
    System.out.println(); // for next line
  }

  /** Method used to display preorder traversal of BST. */
  public void preorder() {
    if (this.root == null) {
      System.out.println("This BST is empty.");
      return;
    }
    System.out.println("Preorder traversal of this tree is:");
    Stack<Node> st = new Stack<Node>();
    st.push(this.root);
    Node temp;
    while (!st.empty()) {
      temp = st.pop();
      System.out.print(temp.data + " ");
      if (temp.right != null) {
        st.push(temp.right);
      }
      if (temp.left != null) {
        st.push(temp.left);
      }
    }
    System.out.println(); // for next line
  }

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

  /** The Node class used for building binary search tree */
  private static class Node {
    int data;
    Node left;
    Node right;

    /** Constructor with data as parameter */
    Node(int d) {
      data = d;
      left = null;
      right = null;
    }
  }
}