Given a Binary Search Tree (BST) and a positive integer k, find the k’th smallest element in the Binary Search Tree.
For example, in the following BST, if k = 3, then output should be 10, and if k = 5, then output should be 14.
We have discussed two methods in this post and one method in this post. All of the previous methods require extra space. How to find the k’th largest element without extra space?
We strongly recommend to minimize your browser and try this yourself first.Implementation
The idea is to use Morris Traversal. 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 for more details.
Below is C++ implementation of the idea.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20find%20k’th%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’s%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” message=”C++ Programming” highlight=”” provider=”manual”/] [ad type=”banner”]Output:
20 30 40 50 60 70 80