text: K 'th Largest element in BST using constant extra space | CPP code for finding K - th largest Node using O ( 1 ) extra memory and reverse Morris traversal . ; Node structure ; helper function to create a new Node ; count variable to keep count of visited Nodes ; if right child is NULL ; first increment count and check if count = k ; otherwise move to the left child ; find inorder successor of current Node ; set left child of successor to the current Node ; move current to its right ; restoring the tree back to original binary search tree removing threaded links ; move current to its left child ; Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> right = temp -> left = NULL ; return temp ; } Node * KthLargestUsingMorrisTraversal ( Node * root , int k ) { Node * curr = root ; Node * Klargest = NULL ; int count = 0 ; while ( curr != NULL ) { if ( curr -> right == NULL ) { if ( ++ count == k ) Klargest = curr ; curr = curr -> left ; } else { Node * succ = curr -> right ; while ( succ -> left != NULL && succ -> left != curr ) succ = succ -> left ; if ( succ -> left == NULL ) { succ -> left = curr ; curr = curr -> right ; } else { succ -> left = NULL ; if ( ++ count == k ) Klargest = curr ; curr = curr -> left ; } } } return Klargest ; } int main ( ) { Node * root = newNode ( 4 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 7 ) ; root -> left -> left = newNode ( 1 ) ; root -> left -> right = newNode ( 3 ) ; root -> right -> left = newNode ( 6 ) ; root -> right -> right = newNode ( 10 ) ; cout << " Finding ▁ K - th ▁ largest ▁ Node ▁ in ▁ BST ▁ : ▁ " << KthLargestUsingMorrisTraversal ( root , 2 ) -> data ; return 0 ; }