K 'th smallest element in BST using O(1) Extra Space | C ++ program to find k 'th largest element in BST ; A BST node ; A function to find ; Count to iterate over elements till we get the kth smallest number ; store the Kth smallest ; to store the current node ; Like Morris traversal if current does not have left child rather than printing as we did in inorder , we will just increment the count as the number will be in an increasing order ; if count is equal to K then we found the kth smallest , so store it in ksmall ; go to current 's right child ; we create links to Inorder Successor and count using these links ; building links ; link made to Inorder Successor ; While breaking the links in so made temporary threaded tree we will check for the K smallest condition ; Revert the changes made in if part ( break link from the Inorder Successor ) ; If count is equal to K then we found the kth smallest and so store it in ksmall ; return the found value ; A utility function to create a new BST node ; A utility function to insert a new node with given key in BST ; If the tree is empty , return a new node ; Otherwise , recur down the tree ; return the ( unchanged ) node pointer ; Driver Program to test above functions ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; Node * left , * right ; } ; int KSmallestUsingMorris ( Node * root , int k ) { int count = 0 ; int ksmall = INT_MIN ; Node * curr = root ; while ( curr != NULL ) { if ( curr -> left == NULL ) { count ++ ; if ( count == k ) ksmall = curr -> key ; curr = curr -> right ; } else { Node * pre = curr -> left ; while ( pre -> right != NULL && pre -> right != curr ) pre = pre -> right ; if ( pre -> right == NULL ) { pre -> right = curr ; curr = curr -> left ; } else { pre -> right = NULL ; count ++ ; if ( count == k ) ksmall = curr -> key ; curr = curr -> right ; } } } return ksmall ; } Node * newNode ( int item ) { Node * temp = new Node ; temp -> key = item ; temp -> left = temp -> right = NULL ; return temp ; } Node * insert ( Node * node , int key ) { if ( node == NULL ) return newNode ( key ) ; if ( key < node -> key ) node -> left = insert ( node -> left , key ) ; else if ( key > node -> key ) node -> right = insert ( node -> right , key ) ; return node ; } int main ( ) { Node * root = NULL ; root = insert ( root , 50 ) ; insert ( root , 30 ) ; insert ( root , 20 ) ; insert ( root , 40 ) ; insert ( root , 70 ) ; insert ( root , 60 ) ; insert ( root , 80 ) ; for ( int k = 1 ; k <= 7 ; k ++ ) cout << KSmallestUsingMorris ( root , k ) << " ▁ " ; return 0 ; }