public static int size(Node node){\n \n if(node==null)return 0;\n int size = 0;\n for(Node child : node.children)\n {\n int childSize = size(child);\n size = size + childSize;\n }\n return size+1 ;\n\n }\n<\/pre>\n\n\n\nHere is the full code :<\/p>\n\n\n\n
import java.io.*;\nimport java.util.*;\n\npublic class Main {\n private static class Node {\n int data;\n ArrayList < Node > children = new ArrayList < > ();\n }\n\n public static void display(Node node) {\n String str = node.data + \" -> \";\n for (Node child: node.children) {\n str += child.data + \", \";\n }\n str += \".\";\n System.out.println(str);\n\n for (Node child: node.children) {\n display(child);\n }\n }\n\n public static Node construct(int[] arr) {\n Node root = null;\n\n Stack < Node > st = new Stack < > ();\n for (int i = 0; i < arr.length; i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node t = new Node();\n t.data = arr[i];\n\n if (st.size() > 0) {\n st.peek().children.add(t);\n } else {\n root = t;\n }\n\n st.push(t);\n }\n }\n\n return root;\n }\n\n public static int size(Node node){\n \n if(node==null)return 0;\n int size = 0;\n for(Node child : node.children)\n {\n int childSize = size(child);\n size = size + childSize;\n }\n return size+1 ;\n\n }\n\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int n = Integer.parseInt(br.readLine());\n int[] arr = new int[n];\n String[] values = br.readLine().split(\" \");\n for (int i = 0; i < n; i++) {\n arr[i] = Integer.parseInt(values[i]);\n }\n\n Node root = construct(arr);\n int sz = size(root);\n System.out.println(\u201cSize : \u201d + sz);\n }\n\n}\n<\/pre>\n\n\n\nInput:<\/strong><\/p>\n\n\n\n12\r\n11 25 -1 37 55 -1 68 -1 -1 41 -1 -1\r<\/code><\/pre>\n\n\n\nOutput:<\/strong><\/p>\n\n\n\nSize : 6\r<\/code><\/pre>\n\n\n\n<\/span>What is Height of a generic tree ?<\/strong><\/span><\/h2>\n\n\n\nNow , let\u2019s learn about the height of generic trees.<\/p>\n\n\n\n
What is Height of a tree and how to calculate the height of a generic tree using java ?<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
For, example consider this tree,<\/p>\n\n\n\n
Height of this tree in terms of edges is 3.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
Taking the example of same above tree,<\/p>\n\n\n\n
Height of the above tree in terms of nodes is 4.<\/p>\n\n\n\n
General Formula for calculator height of a generic tree can be given by :<\/p>\n\n\n\n
Height(tree) = MAX(Height(subtree1),Height(subtree2), \u2026\u2026. , Height(subtreeN) ) + 1<\/p>\n\n\n\n
E.g. Height(10) = MAX(Height(20), Height(30) , Height(40) ) + 1<\/p>\n\n\n\n
Using recursion, our expectation with this function Height(10) = MAX(Height(20), Height(30) , Height(40) ) + 1.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
ALGORITHM<\/strong><\/p>\n\n\n\n- 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).<\/li>
- Build a for loop to calculate Height of each child subtree in the children list.<\/li>
- Compare the height of all subtree child and store the maximum.<\/li>
- Return the max subtree height + 1.<\/li><\/ol>\n\n\n\n
Let\u2019s code the height function :<\/p>\n\n\n\n
public static int height(Node node) {\n\n int max_height = -1; \/\/ it calculates height in terms of edges\n for(Node child : node.children)\n {\n max_height = Math.max(max_height,height(child));\n }\n return max_height+1;\n }\n }\n<\/pre>\n\n\n\nFull code:<\/strong><\/p>\n\n\n\nimport java.io.*;\nimport java.util.*;\n\npublic class Main {\n private static class Node {\n int data;\n ArrayList<Node> children = new ArrayList<>();\n }\n\n public static void display(Node node) {\n String str = node.data + \" -> \";\n for (Node child : node.children) {\n str += child.data + \", \";\n }\n str += \".\";\n System.out.println(str);\n\n for (Node child : node.children) {\n display(child);\n }\n }\n\n public static Node construct(int[] arr) {\n Node root = null;\n\n Stack<Node> st = new Stack<>();\n for (int i = 0; i < arr.length; i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node t = new Node();\n t.data = arr[i];\n\n if (st.size() > 0) {\n st.peek().children.add(t);\n } else {\n root = t;\n }\n\n st.push(t);\n }\n }\n\n return root;\n }\n\n public static int size(Node node) {\n int s = 0;\n\n for (Node child : node.children) {\n s += size(child);\n }\n s += 1;\n\n return s;\n }\n\n public static int max(Node node) {\n int m = Integer.MIN_VALUE;\n\n for (Node child : node.children) {\n int cm = max(child);\n m = Math.max(m, cm);\n }\n m = Math.max(m, node.data);\n\n return m;\n }\n\n public static int height(Node node) {\n\n int max_height = -1;\n for(Node child : node.children)\n {\n max_height = Math.max(max_height,height(child));\n }\n return max_height+1;\n }\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int n = Integer.parseInt(br.readLine());\n int[] arr = new int[n];\n String[] values = br.readLine().split(\" \");\n for (int i = 0; i < n; i++) {\n arr[i] = Integer.parseInt(values[i]);\n }\n\n Node root = construct(arr);\n int h = height(root);\n System.out.println(\u201cHeight of Tree :\u201d + h);\n }\n\n}\n<\/pre>\n\n\n\nInput:<\/p>\n\n\n\n
12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1\r<\/code><\/pre>\n\n\n\nOutput :<\/p>\n\n\n\n
Height of Tree : 2\r<\/code><\/pre>\n\n\n\n<\/span>How To Find Maximum in a generic tree ?<\/strong><\/span><\/h2>\n\n\n\nNow , Let\u2019s learn How to find the maximum in a generic ,<\/p>\n\n\n\n
Maximum with word is self explanatory that we are going to search for the maximum \/ greatest node in the given generic tree.<\/p>\n\n\n\n
Using recursion, the general formula for calculating the maximum is ,<\/p>\n\n\n\n
max ( tree ) = MAX ( tree.data , max(subtree1) , \u2026\u2026\u2026 , max(subtreeN) ) <\/p>\n\n\n\n
For example take this given tree again,<\/p>\n\n\n\n
max (10) = MAX ( 10 , max(20) , max(30) , max(40) )<\/p>\n\n\n\n
Therefore, maximum = 120<\/p>\n\n\n\n
ALGORITHM :\u00a0<\/strong><\/p>\n\n\n\n- Make a max function<\/li>
- Declare and initialise max_child integer variable and assign it with Integer.MIN_VALUE (minimum int value).<\/li>
- Now compare each child from children list using a loop.<\/li>
- Return max between max_child and data of the current parent node.<\/li><\/ol>\n\n\n\n
Now, let\u2019s code the max function :<\/p>\n\n\n\n
public static int max(Node node) {\n \n int max_child = Integer.MIN_VALUE;\n for(Node child:node.children)\n {\n max_child = Math.max(max_child,max(child));\n }\n int d = node.data;\n return Math.max(d,max_child);\n }<\/pre>\n\n\n\nFull Code:<\/strong><\/p>\n\n\n\nimport java.io.*;\nimport java.util.*;\n\npublic class Main {\n private static class Node {\n int data;\n ArrayList<Node> children = new ArrayList<>();\n }\n\n public static void display(Node node) {\n String str = node.data + \" -> \";\n for (Node child : node.children) {\n str += child.data + \", \";\n }\n str += \".\";\n System.out.println(str);\n\n for (Node child : node.children) {\n display(child);\n }\n }\n\n public static Node construct(int[] arr) {\n Node root = null;\n\n Stack<Node> st = new Stack<>();\n for (int i = 0; i < arr.length; i++) {\n if (arr[i] == -1) {\n st.pop();\n } else {\n Node t = new Node();\n t.data = arr[i];\n\n if (st.size() > 0) {\n st.peek().children.add(t);\n } else {\n root = t;\n }\n\n st.push(t);\n }\n }\n\n return root;\n }\n\n public static int size(Node node) {\n int s = 0;\n\n for (Node child : node.children) {\n s += size(child);\n }\n s += 1;\n\n return s;\n }\n\n public static int max(Node node) {\n \n int max_child = Integer.MIN_VALUE;\n for(Node child:node.children)\n {\n max_child = Math.max(max_child,max(child));\n }\n int d = node.data;\n return Math.max(d,max_child);\n }\n\n public static void main(String[] args) throws Exception {\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\n int n = Integer.parseInt(br.readLine());\n int[] arr = new int[n];\n String[] values = br.readLine().split(\" \");\n for (int i = 0; i < n; i++) {\n arr[i] = Integer.parseInt(values[i]);\n }\n\n Node root = construct(arr);\n int m = max(root);\n System.out.println(m);\n \/\/ display(root);\n }\n\n}\n<\/pre>\n\n\n\nInput:<\/strong><\/p>\n\n\n\n12\r\n10 20 -1 30 50 -1 60 -1 -1 40 -1 -1\r<\/code><\/pre>\n\n\n\nOutput:<\/strong><\/p>\n\n\n\n60<\/code><\/pre>\n\n\n\nToday you learn 3 important topics of generic tree and how to implement the t=code of the same.<\/p>\n\n\n\n
Thanks for reading and learning for CodingBroz<\/strong>, for more such articles read more.<\/p>\n\n\n\nBroz Who Code<\/strong><\/p>\n\n\n\nCodingBroz<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"This is a java program to calculate size , height and maximum element in a generic tree. If you don\u2019t know \u201cWhat is a generic tree ?\u201d Learn about the basics of Generic Tree and its implementation in java , here. What is Size of a generic tree ? Size of a tree is the […]<\/p>\n","protected":false},"author":3,"featured_media":572,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"default","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[31,422],"tags":[22,61,95],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/02\/program-to-find-the-size-of-a-generic-tree-codingbroz.png","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/570"}],"collection":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/comments?post=570"}],"version-history":[{"count":3,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/570\/revisions"}],"predecessor-version":[{"id":4945,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/570\/revisions\/4945"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media\/572"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}