C++ Program-K’th smallest element in BST using O(1) Extra Space

K’th 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’th smallest.
Total
8
Shares

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”/]

Output:

20 30 40 50 60 70 80
Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like