package DataStructures.Trees;

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

/**
 * This entire class is used to build a Binary Tree data structure. There is the Node Class and the
 * Tree Class, both explained below.
 */

/**
 * A binary tree is a data structure in which an element has two successors(children). The left
 * child is usually smaller than the parent, and the right child is usually bigger.
 *
 * @author Unknown
 */
public class BinaryTree {

  /**
   * This class implements the nodes that will go on the Binary Tree. They consist of the data in
   * them, the node to the left, the node to the right, and the parent from which they came from.
   *
   * @author Unknown
   */
  static class Node {
    /** Data for the node */
    public int data;
    /** The Node to the left of this one */
    public Node left;
    /** The Node to the right of this one */
    public Node right;
    /** The parent of this node */
    public Node parent;

    /**
     * Constructor of Node
     *
     * @param value Value to put in the node
     */
    public Node(int value) {
      data = value;
      left = null;
      right = null;
      parent = null;
    }
  }

  /** The root of the Binary Tree */
  private Node root;

  /** Constructor */
  public BinaryTree() {
    root = null;
  }

  /** Parameterized Constructor */
  public BinaryTree(Node root) {
    this.root = root;
  }

  /**
   * Method to find a Node with a certain value
   *
   * @param key Value being looked for
   * @return The node if it finds it, otherwise returns the parent
   */
  public Node find(int key) {
    Node current = root;
    while (current != null) {
      if (key < current.data) {
        if (current.left == null) return current; // The key isn't exist, returns the parent
        current = current.left;
      } else if (key > current.data) {
        if (current.right == null) return current;
        current = current.right;
      } else { // If you find the value return it
        return current;
      }
    }
    return null;
  }

  /**
   * Inserts certain value into the Binary Tree
   *
   * @param value Value to be inserted
   */
  public void put(int value) {
    Node newNode = new Node(value);
    if (root == null) root = newNode;
    else {
      // This will return the soon to be parent of the value you're inserting
      Node parent = find(value);

      // This if/else assigns the new node to be either the left or right child of the parent
      if (value < parent.data) {
        parent.left = newNode;
        parent.left.parent = parent;
        return;
      } else {
        parent.right = newNode;
        parent.right.parent = parent;
        return;
      }
    }
  }

  /**
   * Deletes a given value from the Binary Tree
   *
   * @param value Value to be deleted
   * @return If the value was deleted
   */
  public boolean remove(int value) {
    // temp is the node to be deleted
    Node temp = find(value);

    // If the value doesn't exist
    if (temp.data != value) return false;

    // No children
    if (temp.right == null && temp.left == null) {
      if (temp == root) root = null;

      // This if/else assigns the new node to be either the left or right child of the parent
      else if (temp.parent.data < temp.data) temp.parent.right = null;
      else temp.parent.left = null;
      return true;
    }

    // Two children
    else if (temp.left != null && temp.right != null) {
      Node successor = findSuccessor(temp);

      // The left tree of temp is made the left tree of the successor
      successor.left = temp.left;
      successor.left.parent = successor;

      // If the successor has a right child, the child's grandparent is it's new parent
      if (successor.parent != temp) {
        if (successor.right != null) {
          successor.right.parent = successor.parent;
          successor.parent.left = successor.right;
          successor.right = temp.right;
          successor.right.parent = successor;
        } else {
          successor.parent.left = null;
          successor.right = temp.right;
          successor.right.parent = successor;
        }
      }

      if (temp == root) {
        successor.parent = null;
        root = successor;
        return true;
      }

      // If you're not deleting the root
      else {
        successor.parent = temp.parent;

        // This if/else assigns the new node to be either the left or right child of the parent
        if (temp.parent.data < temp.data) temp.parent.right = successor;
        else temp.parent.left = successor;
        return true;
      }
    }
    // One child
    else {
      // If it has a right child
      if (temp.right != null) {
        if (temp == root) {
          root = temp.right;
          return true;
        }

        temp.right.parent = temp.parent;

        // Assigns temp to left or right child
        if (temp.data < temp.parent.data) temp.parent.left = temp.right;
        else temp.parent.right = temp.right;
        return true;
      }
      // If it has a left child
      else {
        if (temp == root) {
          root = temp.left;
          return true;
        }

        temp.left.parent = temp.parent;

        // Assigns temp to left or right side
        if (temp.data < temp.parent.data) temp.parent.left = temp.left;
        else temp.parent.right = temp.left;
        return true;
      }
    }
  }

  /**
   * This method finds the Successor to the Node given. Move right once and go left down the tree as
   * far as you can
   *
   * @param n Node that you want to find the Successor of
   * @return The Successor of the node
   */
  public Node findSuccessor(Node n) {
    if (n.right == null) return n;
    Node current = n.right;
    Node parent = n.right;
    while (current != null) {
      parent = current;
      current = current.left;
    }
    return parent;
  }

  /**
   * Returns the root of the Binary Tree
   *
   * @return the root of the Binary Tree
   */
  public Node getRoot() {
    return root;
  }

  /**
   * Prints leftChild - root - rightChild
   * This is the equivalent of a depth first search
   *
   * @param localRoot The local root of the binary tree
   */
  public void inOrder(Node localRoot) {
    if (localRoot != null) {
      inOrder(localRoot.left);
      System.out.print(localRoot.data + " ");
      inOrder(localRoot.right);
    }
  }

  /**
   * Prints root - leftChild - rightChild
   *
   * @param localRoot The local root of the binary tree
   */
  public void preOrder(Node localRoot) {
    if (localRoot != null) {
      System.out.print(localRoot.data + " ");
      preOrder(localRoot.left);
      preOrder(localRoot.right);
    }
  }

  /**
   * Prints rightChild - leftChild - root
   *
   * @param localRoot The local root of the binary tree
   */
  public void postOrder(Node localRoot) {
    if (localRoot != null) {
      postOrder(localRoot.left);
      postOrder(localRoot.right);
      System.out.print(localRoot.data + " ");
    }
  }

  /**
   * Prints the tree in a breadth first search order
   * This is similar to pre-order traversal, but instead of being
   * implemented with a stack (or recursion), it is implemented
   * with a queue
   * 
   * @param localRoot The local root of the binary tree
   */
  public void bfs(Node localRoot) {
    // Create a queue for the order of the nodes
    Queue<Node> queue = new LinkedList<Node>();
    
    // If the give root is null, then we don't add to the queue
    // and won't do anything
    if (localRoot != null)
      queue.add(localRoot);
    
    // Continue until the queue is empty
    while (! queue.isEmpty()) {
      // Get the next node on the queue to visit
      localRoot = queue.remove();
      
      // Print the data from the node we are visiting
      System.out.print(localRoot.data + " ");

      // Add the children to the queue if not null
      if (localRoot.right != null)
        queue.add(localRoot.right);
      if (localRoot.left != null)
        queue.add(localRoot.left);
    }
  }
}