{"id":566,"date":"2021-02-04T00:40:43","date_gmt":"2021-02-03T19:10:43","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=566"},"modified":"2022-07-01T21:10:59","modified_gmt":"2022-07-01T15:40:59","slug":"generic-n-ary-tree-traversal","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/generic-n-ary-tree-traversal\/","title":{"rendered":"Generic N-ary Tree Traversal"},"content":{"rendered":"\n<p>Traversal in a tree is a process of visiting each node of a tree. We can not randomly access any node. As every node in a tree is connected through edges, we need to start from the root node to traverse the node. There are many ways to traverse a generic tree ( N-ary tree) but we will be discussing 2 of the commonly used traversals :<\/p>\n\n\n\n<ol><li>Pre-Order traversal<\/li><li>Post-Order traversal<\/li><\/ol>\n\n\n\n<p>Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img fetchpriority=\"high\" decoding=\"async\" width=\"1167\" height=\"675\" src=\"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/02\/generic-tree-traversal-in-java-codingbroz.png\" alt=\"Generic N-ary Tree Traversal\" class=\"wp-image-568\" srcset=\"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/02\/generic-tree-traversal-in-java-codingbroz.png 1167w, https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/02\/generic-tree-traversal-in-java-codingbroz-768x444.png 768w\" sizes=\"(max-width: 1167px) 100vw, 1167px\" \/><\/figure>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<label for=\"ez-toc-cssicon-toggle-item-662d5df7b17d0\" class=\"ez-toc-cssicon-toggle-label\"><label class=\"ez-toc-title\">Table of Contents<\/label>\n<span class=\"ez-toc-cssicon\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #0090ff;color:#0090ff\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #0090ff;color:#0090ff\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-662d5df7b17d0\" checked \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.codingbroz.com\/generic-n-ary-tree-traversal\/#What_is_Pre-Order_Traversal_in_a_Generic_Tree\" title=\"What is Pre-Order Traversal in a Generic Tree ?\">What is Pre-Order Traversal in a Generic Tree ?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.codingbroz.com\/generic-n-ary-tree-traversal\/#What_is_Post-Order_Traversal_in_a_Generic_Tree_N-ary_Tree\" title=\"What is Post-Order Traversal in a Generic Tree ( N-ary Tree) ?\">What is Post-Order Traversal in a Generic Tree ( N-ary Tree) ?<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"What_is_Pre-Order_Traversal_in_a_Generic_Tree\"><\/span><strong>What is Pre-Order Traversal in a Generic Tree ?<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Pre-Order Traversal method in generic trees means the first visit of every node in the euler path.\u00a0We can also say that when we are on the left side of the node in the euler.\u00a0<\/p>\n\n\n\n<p>Take this example<\/p>\n\n\n\n<p>Starting from the Root 10 , and following the pre-order , we print 10 and then move towards the first child 20 print it, then the next child 30 and print it ,now&nbsp; in 30 we first visit its first child 50 print it then move to 60 print it and now the last child of 10 i.e. 40 is visited and printed.<\/p>\n\n\n\n<p>We print the nodes in the first visited i.e. when the euler is in the left.<\/p>\n\n\n\n<p>For example, see this :<\/p>\n\n\n\n<p>So, the output for the Pre-Order Traversal will be :<\/p>\n\n\n\n<p class=\"has-text-align-center\"><strong>10 -> 20 -> 30 -> 50 -> 60 -> 40.<\/strong><\/p>\n\n\n\n<p><strong>ALGORITHM :<\/strong><\/p>\n\n\n\n<p>preOrder( root )<\/p>\n\n\n\n<ol><li>Visit\/Print the root<\/li><li>Recursively traverse all the child sub trees.<\/li><\/ol>\n\n\n\n<p>Let\u2019s code preOrder function implementation in java :<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void preOrder(Node node){\n    \/\/ Preorder traversal\n    if(node == null) return;\n    System.out.println(node.data);\n    for(Node child:node.children)\n    {\n        preOrder(child);\n    }\n  }\n<\/pre>\n\n\n\n<p>Now, Let\u2019s move towards the post order traversal in a generic tree.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"What_is_Post-Order_Traversal_in_a_Generic_Tree_N-ary_Tree\"><\/span><strong>What is Post-Order Traversal in a Generic Tree ( N-ary Tree) ?<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Pre-Order Traversal method in generic trees means the last visit of every node in the euler path.We can also say that when we are on the right side of the node in the euler.\u00a0<\/p>\n\n\n\n<p>Take this example :<\/p>\n\n\n\n<p>Starting from the Root 10 , and following the post-order traversal, we move towards the first child 20 and when exiting print it, then the next child 30,now in 30 we first visit its first child 50 and on exiting print it then move to 60 and on exiting print it and now print 30 while exiting it. Now we visit 40 and print it on exiting and at last print the root node 10.<\/p>\n\n\n\n<p>We print the nodes in the last visit i.e. when the euler is on the right.<\/p>\n\n\n\n<p>For example, see this :<\/p>\n\n\n\n<p>So, the output for the Post-Order Traversal will be :<\/p>\n\n\n\n<p class=\"has-text-align-center\"><strong>20 -> 50 -> 60 -> 30 -> 40 -> 10 .<\/strong><\/p>\n\n\n\n<p><strong>ALGORITHM :<\/strong><\/p>\n\n\n\n<p>postOrder( root )<\/p>\n\n\n\n<ol><li>Recursively traverse the children.<\/li><li>Print the node.<\/li><\/ol>\n\n\n\n<p>Let\u2019s code preOrder function implementation in java :<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static void postOrder(Node node){\n    \/\/ Preorder traversal\n    if(node == null) return;\n    for(Node child:node.children)\n    {\n        postOrder(child);\n    }\n   System.out.println(node.data);\n  }\n<\/pre>\n\n\n\n<p>Thanks for reading and learning from CodingBroz. Learn more about Generic Tree (N-ary Tree) from here.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Traversal in a tree is a process of visiting each node of a tree. We can not randomly access any node. As every node in a tree is connected through edges, we need to start from the root node to traverse the node. There are many ways to traverse a generic tree ( N-ary tree) [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":568,"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,94],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/www.codingbroz.com\/wp-content\/uploads\/2021\/02\/generic-tree-traversal-in-java-codingbroz.png","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/566"}],"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=566"}],"version-history":[{"count":2,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/566\/revisions"}],"predecessor-version":[{"id":569,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/566\/revisions\/569"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media\/568"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=566"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=566"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=566"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}