package DataStructures.Trees;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * A generic tree is a tree which can have as many children as it can be It might be possible that
 * every node present is directly connected to root node.
 *
 * <p>In this code Every function has two copies: one function is helper function which can be
 * called from main and from that function a private function is called which will do the actual
 * work. I have done this, while calling from main one have to give minimum parameters.
 */
public class GenericTree {
  private class Node {
    int data;
    ArrayList<Node> child = new ArrayList<>();
  }

  private Node root;
  private int size;

  public GenericTree() { // Constructor
    Scanner scn = new Scanner(System.in);
    root = create_treeG(null, 0, scn);
  }

  private Node create_treeG(Node node, int childindx, Scanner scn) {
    // display
    if (node == null) {
      System.out.println("Enter root's data");
    } else {
      System.out.println("Enter data of parent of index " + node.data + " " + childindx);
    }
    // input
    node = new Node();
    node.data = scn.nextInt();
    System.out.println("number of children");
    int number = scn.nextInt();
    for (int i = 0; i < number; i++) {
      Node child = create_treeG(node, i, scn);
      size++;
      node.child.add(child);
    }
    return node;
  }

  /** Function to display the generic tree */
  public void display() { // Helper function
    display_1(root);
  }

  private void display_1(Node parent) {
    System.out.print(parent.data + "=>");
    for (int i = 0; i < parent.child.size(); i++) {
      System.out.print(parent.child.get(i).data + " ");
    }
    System.out.println(".");
    for (int i = 0; i < parent.child.size(); i++) {
      display_1(parent.child.get(i));
    }
  }

  /**
   * One call store the size directly but if you are asked compute size this function to calculate
   * size goes as follows
   *
   * @return size
   */
  public int size2call() {
    return size2(root);
  }

  public int size2(Node roott) {
    int sz = 0;
    for (int i = 0; i < roott.child.size(); i++) {
      sz += size2(roott.child.get(i));
    }
    return sz + 1;
  }

  /**
   * Function to compute maximum value in the generic tree
   *
   * @return maximum value
   */
  public int maxcall() {
    int maxi = root.data;
    return max(root, maxi);
  }

  private int max(Node roott, int maxi) {
    if (maxi < roott.data) maxi = roott.data;
    for (int i = 0; i < roott.child.size(); i++) {
      maxi = max(roott.child.get(i), maxi);
    }

    return maxi;
  }

  /**
   * Function to compute HEIGHT of the generic tree
   *
   * @return height
   */
  public int heightcall() {
    return height(root) - 1;
  }

  private int height(Node node) {
    int h = 0;
    for (int i = 0; i < node.child.size(); i++) {
      int k = height(node.child.get(i));
      if (k > h) h = k;
    }
    return h + 1;
  }

  /**
   * Function to find whether a number is present in the generic tree or not
   *
   * @param info number
   * @return present or not
   */
  public boolean findcall(int info) {
    return find(root, info);
  }

  private boolean find(Node node, int info) {
    if (node.data == info) return true;
    for (int i = 0; i < node.child.size(); i++) {
      if (find(node.child.get(i), info)) return true;
    }
    return false;
  }

  /**
   * Function to calculate depth of generic tree
   *
   * @param dep depth
   */
  public void depthcaller(int dep) {
    depth(root, dep);
  }

  public void depth(Node node, int dep) {
    if (dep == 0) {
      System.out.println(node.data);
      return;
    }
    for (int i = 0; i < node.child.size(); i++) depth(node.child.get(i), dep - 1);
    return;
  }

  /** Function to print generic tree in pre-order */
  public void preordercall() {
    preorder(root);
    System.out.println(".");
  }

  private void preorder(Node node) {
    System.out.print(node.data + " ");
    for (int i = 0; i < node.child.size(); i++) preorder(node.child.get(i));
  }

  /** Function to print generic tree in post-order */
  public void postordercall() {
    postorder(root);
    System.out.println(".");
  }

  private void postorder(Node node) {
    for (int i = 0; i < node.child.size(); i++) postorder(node.child.get(i));
    System.out.print(node.data + " ");
  }

  /** Function to print generic tree in level-order */
  public void levelorder() {
    LinkedList<Node> q = new LinkedList<>();
    q.addLast(root);
    while (!q.isEmpty()) {
      int k = q.getFirst().data;
      System.out.print(k + " ");

      for (int i = 0; i < q.getFirst().child.size(); i++) {
        q.addLast(q.getFirst().child.get(i));
      }
      q.removeFirst();
    }
    System.out.println(".");
  }

  /** Function to remove all leaves of generic tree */
  public void removeleavescall() {
    removeleaves(root);
  }

  private void removeleaves(Node node) {
    ArrayList<Integer> arr = new ArrayList<>();
    for (int i = 0; i < node.child.size(); i++) {
      if (node.child.get(i).child.size() == 0) {
        arr.add(i);
        // node.child.remove(i);
        // i--;
      } else removeleaves(node.child.get(i));
    }
    for (int i = arr.size() - 1; i >= 0; i--) {
      node.child.remove(arr.get(i) + 0);
    }
  }
}