Program to find the Size,Height and the Maximum in a Generic Tree

This is a java program to calculate size , height and maximum element in a generic tree. If you don’t know “What is a generic tree ?” Learn about the basics of Generic Tree and its implementation in java , here.

Program to find the Size,Height and the Maximum in a Generic Tree

What is Size of a generic tree ?

Size of a tree is the total number of nodes present in the tree. Take the following example of a generic tree.

Size of this generic tree is 12.

The Basic formula of calculating the Size of a generic tree is given by :

Size(tree) = Size(child subtree 1) + Size(child subtree2) + ………. + 1(counting itself)

Taking the example of the above tree , formula goes like :

Size(10) = Size(20) + Size(30) + Size(40) + 1 = 3 + 6 + 2 +1 = 12.

Using recursion, our expectation is the function Size(10) = Size(20) + Size(30) + Size(40) + 1.

And our faith is that function Size(40),Size(30),Size(20) knows how to calculate their size. Then we add 1 in the Result, which calculates the size of our generic tree.

ALGORITHM :

  1. Declare a size function
  2. Check if the node is null return 0.
  3. Declare an int variable named size
  4. Traverse each child from children arraylist using for loop, and for each child calculate the child size and add it in size.
  5. At last add 1 in the size 
  6. Return the size

Let’s move towards the sum function :

public static int size(Node node){
   
    if(node==null)return 0;
    int size = 0;
    for(Node child : node.children)
    {
        int childSize = size(child);
        size = size + childSize;
    }
    return size+1 ;

  }

Here is the full code :

import java.io.*;
import java.util.*;

public class Main {
    private static class Node {
        int data;
        ArrayList < Node > children = new ArrayList < > ();
    }

    public static void display(Node node) {
        String str = node.data + " -> ";
        for (Node child: node.children) {
            str += child.data + ", ";
        }
        str += ".";
        System.out.println(str);

        for (Node child: node.children) {
            display(child);
        }
    }

    public static Node construct(int[] arr) {
        Node root = null;

        Stack < Node > st = new Stack < > ();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }

                st.push(t);
            }
        }

        return root;
    }

    public static int size(Node node){
   
    if(node==null)return 0;
    int size = 0;
    for(Node child : node.children)
    {
        int childSize = size(child);
        size = size + childSize;
    }
    return size+1 ;

  }


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }

        Node root = construct(arr);
        int sz = size(root);
        System.out.println(“Size : ” + sz);
        }

}

Input:

12
11 25 -1 37 55 -1 68 -1 -1 41 -1 -1

Output:

Size : 6

What is Height of a generic tree ?

Now , let’s learn about the height of generic trees.

What is Height of a tree and how to calculate the height of a generic tree using java ?

If we calculate height in terms of edges then, Height of a tree is the number of edges in the longest downward path from root to the leaf node.

For, example consider this tree,

Height of this tree in terms of edges is 3.

If we calculate Height of a tree in terms of the nodes, then Height of a tree is the number of nodes in the longest downward path from root to the leaf node.

Taking the example of same above tree,

Height of the above tree in terms of nodes is 4.

General Formula for calculator height of a generic tree can be given by :

Height(tree) = MAX(Height(subtree1),Height(subtree2), ……. , Height(subtreeN) ) + 1

E.g.  Height(10) = MAX(Height(20), Height(30) , Height(40) ) + 1

Using recursion, our expectation with this function Height(10) = MAX(Height(20), Height(30) , Height(40) ) + 1.

And our faith is that function Height(20), Height(30) , Height(40) knows how to calculate their height. Then we add 1 in the Result, which calculates the height of our generic tree.

ALGORITHM

  1. In function height, declare an integer named ht and initialise it with -1 (to calc. Height in terms of edges ) or 0 (calc. Height in terms of node).
  2. Build a for loop to calculate Height of each child subtree in the children list.
  3. Compare the height of all subtree child and store the maximum.
  4. Return the max subtree height + 1.

Let’s code the height function :

public static int height(Node node) {

        int max_height = -1; // it calculates height in terms of edges
        for(Node child : node.children)
        {
            max_height = Math.max(max_height,height(child));
        }
        return max_height+1;
    }
  }

Full code:

import java.io.*;
import java.util.*;

public class Main {
  private static class Node {
    int data;
    ArrayList<Node> children = new ArrayList<>();
  }

  public static void display(Node node) {
    String str = node.data + " -> ";
    for (Node child : node.children) {
      str += child.data + ", ";
    }
    str += ".";
    System.out.println(str);

    for (Node child : node.children) {
      display(child);
    }
  }

  public static Node construct(int[] arr) {
    Node root = null;

    Stack<Node> st = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == -1) {
        st.pop();
      } else {
        Node t = new Node();
        t.data = arr[i];

        if (st.size() > 0) {
          st.peek().children.add(t);
        } else {
          root = t;
        }

        st.push(t);
      }
    }

    return root;
  }

  public static int size(Node node) {
    int s = 0;

    for (Node child : node.children) {
      s += size(child);
    }
    s += 1;

    return s;
  }

  public static int max(Node node) {
    int m = Integer.MIN_VALUE;

    for (Node child : node.children) {
      int cm = max(child);
      m = Math.max(m, cm);
    }
    m = Math.max(m, node.data);

    return m;
  }

  public static int height(Node node) {

        int max_height = -1;
        for(Node child : node.children)
        {
            max_height = Math.max(max_height,height(child));
        }
        return max_height+1;
    }
  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    String[] values = br.readLine().split(" ");
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(values[i]);
    }

    Node root = construct(arr);
    int h = height(root);
    System.out.println(“Height of Tree :” + h);
      }

}

Input:

12
10 20 -1 30 50 -1 60 -1 -1 40 -1 -1

Output :

Height of Tree : 2

How To Find Maximum in a generic tree ?

Now , Let’s learn How to find the maximum in a generic ,

Maximum with word is self explanatory that we are going to search for the maximum / greatest node in the given generic tree.

Using recursion, the general formula for calculating the maximum is ,

max ( tree ) = MAX ( tree.data , max(subtree1) , ……… , max(subtreeN) ) 

For example take this given tree again,

max (10) = MAX ( 10 , max(20) , max(30) , max(40) )

Therefore, maximum = 120

ALGORITHM : 

  1. Make a max function
  2. Declare and initialise max_child integer variable and assign it with Integer.MIN_VALUE (minimum int value).
  3. Now compare each child from children list using a loop.
  4. Return max between max_child and data of the current parent node.

Now, let’s code the max function :

public static int max(Node node) {
    
    int max_child = Integer.MIN_VALUE;
    for(Node child:node.children)
    {
        max_child = Math.max(max_child,max(child));
    }
    int d = node.data;
    return Math.max(d,max_child);
  }

Full Code:

import java.io.*;
import java.util.*;

public class Main {
  private static class Node {
    int data;
    ArrayList<Node> children = new ArrayList<>();
  }

  public static void display(Node node) {
    String str = node.data + " -> ";
    for (Node child : node.children) {
      str += child.data + ", ";
    }
    str += ".";
    System.out.println(str);

    for (Node child : node.children) {
      display(child);
    }
  }

  public static Node construct(int[] arr) {
    Node root = null;

    Stack<Node> st = new Stack<>();
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] == -1) {
        st.pop();
      } else {
        Node t = new Node();
        t.data = arr[i];

        if (st.size() > 0) {
          st.peek().children.add(t);
        } else {
          root = t;
        }

        st.push(t);
      }
    }

    return root;
  }

  public static int size(Node node) {
    int s = 0;

    for (Node child : node.children) {
      s += size(child);
    }
    s += 1;

    return s;
  }

  public static int max(Node node) {
    
    int max_child = Integer.MIN_VALUE;
    for(Node child:node.children)
    {
        max_child = Math.max(max_child,max(child));
    }
    int d = node.data;
    return Math.max(d,max_child);
  }

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] arr = new int[n];
    String[] values = br.readLine().split(" ");
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.parseInt(values[i]);
    }

    Node root = construct(arr);
    int m = max(root);
    System.out.println(m);
    // display(root);
  }

}

Input:

12
10 20 -1 30 50 -1 60 -1 -1 40 -1 -1

Output:

60

Today you learn 3 important topics of generic tree and how to implement the t=code of the same.

Thanks for reading and learning for CodingBroz, for more such articles read more.

Broz Who Code

CodingBroz

Leave a Comment

Your email address will not be published. Required fields are marked *