{"id":27144,"date":"2018-01-03T21:50:24","date_gmt":"2018-01-03T16:20:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27144"},"modified":"2018-01-03T21:50:24","modified_gmt":"2018-01-03T16:20:24","slug":"java-program-level-order-tree-traversal","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-program-level-order-tree-traversal\/","title":{"rendered":"java program – Level Order Tree Traversal"},"content":{"rendered":"

Level order traversal of a tree is breadth first traversal for the tree.<\/p>\n

Level order traversal of the above tree is 1 2 3 4 5<\/p>\n

\n

Recommended: Please solve it on \u201cPRACTICE<\/u><\/i><\/b>\u201d first,<\/h2>\n

before moving on to the solution.<\/h2>\n<\/div>\n

METHOD 1 (Use function to print a given level)<\/strong><\/p>\n

Algorithm:<\/strong>
\nThere are basically two functions in this method. One is to print all nodes at a given level (printGivenLevel), and other is to print level order traversal of the tree (printLevelorder). printLevelorder makes use of printGivenLevel to print nodes at all levels one by one starting from root.<\/p>\n

\/*Function to print level order traversal of tree*\/\r\nprintLevelorder(tree)<\/strong>\r\nfor d = 1 to height(tree)\r\n   printGivenLevel(tree, d);\r\n\r\n\/*Function to print all nodes at a given level*\/\r\nprintGivenLevel(tree, level)<\/strong>\r\nif tree is NULL then return;\r\nif level is 1, then\r\n    print(tree->data);\r\nelse if level greater than 1, then\r\n    printGivenLevel(tree->left, level-1);\r\n    printGivenLevel(tree->right, level-1);<\/pre>\n[ad type=\u201dbanner\u201d]\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Recursive%20Java%20program%20for%20level%20order%20traversal%20of%20Binary%20Tree%0A%20%0A%2F*%20Class%20containing%20left%20and%20right%20child%20of%20current%20%0A%20%20%20node%20and%20key%20value*%2F%0Aclass%20Node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20Node%20left%2C%20right%3B%0A%20%20%20%20public%20Node(int%20item)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20data%20%3D%20item%3B%0A%20%20%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0Aclass%20BinaryTree%0A%7B%0A%20%20%20%20%2F%2F%20Root%20of%20the%20Binary%20Tree%0A%20%20%20%20Node%20root%3B%0A%20%0A%20%20%20%20public%20BinaryTree()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20null%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20function%20to%20print%20level%20order%20traversal%20of%20tree*%2F%0A%20%20%20%20void%20printLevelOrder()%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20h%20%3D%20height(root)%3B%0A%20%20%20%20%20%20%20%20int%20i%3B%0A%20%20%20%20%20%20%20%20for%20(i%3D1%3B%20i%3C%3Dh%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root%2C%20i)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Compute%20the%20%22height%22%20of%20a%20tree%20\u2013%20the%20number%20of%0A%20%20%20%20nodes%20along%20the%20longest%20path%20from%20the%20root%20node%0A%20%20%20%20down%20to%20the%20farthest%20leaf%20node.*%2F%0A%20%20%20%20int%20height(Node%20root)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20return%200%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20compute%20%20height%20of%20each%20subtree%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20lheight%20%3D%20height(root.left)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20int%20rheight%20%3D%20height(root.right)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F*%20use%20the%20larger%20one%20*%2F%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(lheight%20%3E%20rheight)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return(lheight%2B1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20return(rheight%2B1)%3B%20%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Print%20nodes%20at%20the%20given%20level%20*%2F%0A%20%20%20%20void%20printGivenLevel%20(Node%20root%20%2Cint%20level)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(root%20%3D%3D%20null)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20if%20(level%20%3D%3D%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(root.data%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20else%20if%20(level%20%3E%201)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root.left%2C%20level-1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20printGivenLevel(root.right%2C%20level-1)%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20Driver%20program%20to%20test%20above%20functions%20*%2F%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20BinaryTree%20tree%20%3D%20new%20BinaryTree()%3B%0A%20%20%20%20%20%20%20tree.root%3D%20new%20Node(1)%3B%0A%20%20%20%20%20%20%20tree.root.left%3D%20new%20Node(2)%3B%0A%20%20%20%20%20%20%20tree.root.right%3D%20new%20Node(3)%3B%0A%20%20%20%20%20%20%20tree.root.left.left%3D%20new%20Node(4)%3B%0A%20%20%20%20%20%20%20tree.root.left.right%3D%20new%20Node(5)%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20System.out.println(%22Level%20order%20traversal%20of%20binary%20tree%20is%20%22)%3B%0A%20%20%20%20%20%20%20tree.printLevelOrder()%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n","protected":false},"excerpt":{"rendered":"
java program – Level Order Tree Traversal – Level order traversal of tree is breadth first traversal for the tree. There are basically two functions <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80140,1,2139],"tags":[80965,80963,80964,80908,80903,80906,80962,80966],"class_list":["post-27144","post","type-post","status-publish","format-standard","hentry","category-binay-tree","category-coding","category-java","tag-binary-tree-level-order-traversal-ii","tag-binary-tree-level-order-traversal-java","tag-binary-tree-level-order-traversal-leetcode","tag-level-order-traversal-example","tag-level-order-traversal-of-a-binary-tree-in-c-code","tag-level-order-traversal-of-binary-tree-using-queue-in-c","tag-level-order-traversal-using-queue","tag-zigzag-level-order-traversal"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27144","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27144"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27144\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27144"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27144"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27144"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}