{"id":27375,"date":"2018-02-02T20:54:39","date_gmt":"2018-02-02T15:24:39","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27375"},"modified":"2018-02-02T20:54:39","modified_gmt":"2018-02-02T15:24:39","slug":"c-program-kth-smallest-element-bst-using-o1-extra-space","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-program-kth-smallest-element-bst-using-o1-extra-space\/","title":{"rendered":"C++ Program-K\u2019th smallest element in BST using O(1) Extra Space"},"content":{"rendered":"

Given a Binary Search Tree (BST) and a positive integer k, find the k\u2019th smallest element in the Binary Search Tree.<\/span><\/p>\n

For example, in the following BST, if k = 3, then output should be 10, and if k = 5, then output should be 14.<\/p>\n

We have discussed two methods in this <\/a>post and one method in this <\/a>post. All of the previous methods require extra space. How to find the k\u2019th largest element without extra space?<\/p>\n

We strongly recommend to minimize your browser and try this yourself first.<\/strong>Implementation<\/strong><\/p>\n

The idea is to use Morris Traversal<\/a>. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree. See this <\/a>for more details.<\/p>\n

Below is C++ implementation of the idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20C%2B%2B%20program%20to%20find%20k\u2019th%20largest%20element%20in%20BST%0A%23include%3Ciostream%3E%0A%23include%3Cclimits%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20BST%20node%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20key%3B%0A%20%20%20%20Node%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20function%20to%20find%0Aint%20KSmallestUsingMorris(Node%20*root%2C%20int%20k)%0A%7B%0A%20%20%20%20%2F%2F%20Count%20to%20iterate%20over%20elements%20till%20we%0A%20%20%20%20%2F%2F%20get%20the%20kth%20smallest%20number%0A%20%20%20%20int%20count%20%3D%200%3B%0A%20%0A%20%20%20%20int%20ksmall%20%3D%20INT_MIN%3B%20%2F%2F%20store%20the%20Kth%20smallest%0A%20%20%20%20Node%20*curr%20%3D%20root%3B%20%2F%2F%20to%20store%20the%20current%20node%0A%20%0A%20%20%20%20while%20(curr%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Like%20Morris%20traversal%20if%20current%20does%0A%20%20%20%20%20%20%20%20%2F%2F%20not%20have%20left%20child%20rather%20than%20printing%0A%20%20%20%20%20%20%20%20%2F%2F%20as%20we%20did%20in%20inorder%2C%20we%20will%20just%0A%20%20%20%20%20%20%20%20%2F%2F%20increment%20the%20count%20as%20the%20number%20will%0A%20%20%20%20%20%20%20%20%2F%2F%20be%20in%20an%20increasing%20order%0A%20%20%20%20%20%20%20%20if%20(curr-%3Eleft%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20if%20count%20is%20equal%20to%20K%20then%20we%20found%20the%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20kth%20smallest%2C%20so%20store%20it%20in%20ksmall%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(count%3D%3Dk)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ksmall%20%3D%20curr-%3Ekey%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20go%20to%20current\u2019s%20right%20child%0A%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20curr-%3Eright%3B%0A%20%20%20%20%20%20%20%20%7D%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%2F%20we%20create%20links%20to%20Inorder%20Successor%20and%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20count%20using%20these%20links%0A%20%20%20%20%20%20%20%20%20%20%20%20Node%20*pre%20%3D%20curr-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20(pre-%3Eright%20!%3D%20NULL%20%26%26%20pre-%3Eright%20!%3D%20curr)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre%20%3D%20pre-%3Eright%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20building%20links%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(pre-%3Eright%3D%3DNULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2Flink%20made%20to%20Inorder%20Successor%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre-%3Eright%20%3D%20curr%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20curr-%3Eleft%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20While%20breaking%20the%20links%20in%20so%20made%20temporary%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20threaded%20tree%20we%20will%20check%20for%20the%20K%20smallest%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20condition%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Revert%20the%20changes%20made%20in%20if%20part%20(break%20link%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20from%20the%20Inorder%20Successor)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20pre-%3Eright%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20count%20is%20equal%20to%20K%20then%20we%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20the%20kth%20smallest%20and%20so%20store%20it%20in%20ksmall%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(count%3D%3Dk)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ksmall%20%3D%20curr-%3Ekey%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20curr%20%3D%20curr-%3Eright%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20return%20ksmall%3B%20%2F%2Freturn%20the%20found%20value%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20BST%20node%0ANode%20*newNode(int%20item)%0A%7B%0A%20%20%20%20Node%20*temp%20%3D%20new%20Node%3B%0A%20%20%20%20temp-%3Ekey%20%3D%20item%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F*%20A%20utility%20function%20to%20insert%20a%20new%20node%20with%20given%20key%20in%20BST%20*%2F%0ANode*%20insert(Node*%20node%2C%20int%20key)%0A%7B%0A%20%20%20%20%2F*%20If%20the%20tree%20is%20empty%2C%20return%20a%20new%20node%20*%2F%0A%20%20%20%20if%20(node%20%3D%3D%20NULL)%20return%20newNode(key)%3B%0A%20%0A%20%20%20%20%2F*%20Otherwise%2C%20recur%20down%20the%20tree%20*%2F%0A%20%20%20%20if%20(key%20%3C%20node-%3Ekey)%0A%20%20%20%20%20%20%20%20node-%3Eleft%20%20%3D%20insert(node-%3Eleft%2C%20key)%3B%0A%20%20%20%20else%20if%20(key%20%3E%20node-%3Ekey)%0A%20%20%20%20%20%20%20%20node-%3Eright%20%3D%20insert(node-%3Eright%2C%20key)%3B%0A%20%0A%20%20%20%20%2F*%20return%20the%20(unchanged)%20node%20pointer%20*%2F%0A%20%20%20%20return%20node%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20Program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20create%20following%20BST%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%2050%0A%20%20%20%20%20%20%20%20%20%20%20%2F%20%20%20%20%20%5C%0A%20%20%20%20%20%20%20%20%20%2030%20%20%20%20%20%2070%0A%20%20%20%20%20%20%20%20%20%2F%20%20%5C%20%20%20%20%2F%20%20%5C%0A%20%20%20%20%20%20%2020%20%20%2040%20%2060%20%20%2080%20*%2F%0A%20%20%20%20Node%20*root%20%3D%20NULL%3B%0A%20%20%20%20root%20%3D%20insert(root%2C%2050)%3B%0A%20%20%20%20insert(root%2C%2030)%3B%0A%20%20%20%20insert(root%2C%2020)%3B%0A%20%20%20%20insert(root%2C%2040)%3B%0A%20%20%20%20insert(root%2C%2070)%3B%0A%20%20%20%20insert(root%2C%2060)%3B%0A%20%20%20%20insert(root%2C%2080)%3B%0A%20%0A%20%20%20%20for%20(int%20k%3D1%3B%20k%3C%3D7%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20cout%20%3C%3C%20KSmallestUsingMorris(root%2C%20k)%20%3C%3C%20%22%20%22%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n

Output:<\/strong><\/p>\n

20 30 40 50 60 70 80<\/pre>\n","protected":false},"excerpt":{"rendered":"
K\u2019th smallest element in BST using O(1) Extra Space – Binary Search Tree – Given a Binary Search Tree (BST) and positive integer k, find the k\u2019th smallest.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[80126,83515],"tags":[81505,81338,81507,81334,81337,81331,81335,81332,81506,81333,81330],"class_list":["post-27375","post","type-post","status-publish","format-standard","hentry","category-binary-search-tree","category-c-programming-3","tag-2-sum-binary-tree","tag-algorithm-to-find-pair-of-numbers-whose-sum-is-equal-to-k","tag-c-program-kth-smallest-element-in-bst-using-o1-extra-space","tag-find-the-second-largest-element-in-a-binary-search-tree","tag-given-an-array-and-a-number-k","tag-kth-largest-element-in-bst-java","tag-kth-smallest-element-in-a-array","tag-kth-smallest-element-in-a-bst-c","tag-kth-smallest-element-in-a-bst-leetcode-c","tag-kth-smallest-element-in-a-bst-recursive","tag-kth-smallest-element-in-bst-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27375","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=27375"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27375\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27375"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27375"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27375"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}