{"id":27253,"date":"2018-01-05T22:08:37","date_gmt":"2018-01-05T16:38:37","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27253"},"modified":"2018-01-05T22:08:37","modified_gmt":"2018-01-05T16:38:37","slug":"sorted-order-printing-given-array-represents-bst","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/sorted-order-printing-given-array-represents-bst\/","title":{"rendered":"Sorted order printing of a given array that represents a BST"},"content":{"rendered":"<p>Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order.<span id=\"more-9514\"><\/span><\/p>\n<p>For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5<\/p>\n<p><strong>Solution:<\/strong><br \/>\nInorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in <a href=\"http:\/\/www.geeksforgeeks.org\/?p=618\">standard Inorder Tree Traversal<\/a>.<\/p>\n<p><strong>Implementation:<\/strong><\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%23include%3Cstdio.h%3E%0A%20%0Avoid%20printSorted(int%20arr%5B%5D%2C%20int%20start%2C%20int%20end)%0A%7B%20%20%20%20%20%0A%20%20if(start%20%3E%20end)%0A%20%20%20%20return%3B%0A%20%0A%20%20%2F%2F%20print%20left%20subtree%0A%20%20printSorted(arr%2C%20start*2%20%2B%201%2C%20end)%3B%0A%20%0A%20%20%2F%2F%20print%20root%0A%20%20printf(%22%25d%20%20%22%2C%20arr%5Bstart%5D)%3B%0A%20%0A%20%20%2F%2F%20print%20right%20subtree%0A%20%20printSorted(arr%2C%20start*2%20%2B%202%2C%20end)%3B%20%20%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B4%2C%202%2C%205%2C%201%2C%203%7D%3B%0A%20%20int%20arr_size%20%3D%20sizeof(arr)%2Fsizeof(int)%3B%0A%20%20printSorted(arr%2C%200%2C%20arr_size-1)%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D\u201d message=\u201dC Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Time Complexity:<\/strong> O(n)<\/p>\n<p>Please write comments if you find the above solution incorrect, or find better ways to solve the same problem.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Sorted order printing of a given array that represents a BST &#8211; Binary Search Tree &#8211; Given an array that stores a complete Binary Search Tree,<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,80126],"tags":[80546,80539,70263,70669,70300,70284,70277,73310,73309,80557,70268,80573,80818,70285,80710,81264],"class_list":["post-27253","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binary-search-tree","tag-application-of-binary-tree","tag-binary-search-algorithm-c","tag-binary-search-tree","tag-binary-search-tree-applications","tag-binary-search-tree-in-c","tag-binary-search-tree-in-data-structure","tag-binary-search-tree-java","tag-binary-search-tree-program-in-c","tag-binary-search-tree-traversal","tag-binary-search-tree-with-example","tag-binary-tree","tag-binary-tree-search-java","tag-binary-tree-simulator","tag-binary-tree-traversal","tag-binary-tree-traversal-program-in-c","tag-pre-order-traversal-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27253","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=27253"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27253\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}