GenericTree.java

package com.thealgorithms.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 static final class Node {

 int data;
 ArrayList<Node> child = new ArrayList<>();
 }

 private final Node root;

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

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

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

 private void display1(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++) {
 display1(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);
 }
 }

 /**
 * 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);
 } else {
 removeleaves(node.child.get(i));
 }
 }
 for (int i = arr.size() - 1; i >= 0; i--) {
 node.child.remove(arr.get(i) + 0);
 }
 }
}