K 'th Largest element in BST using constant extra space | Java Program 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 ; Driver code ; Constructed binary tree is 4 / \ 2 7 / \ / \ 1 3 6 10
class GfG { static class Node { int data ; Node left , right ; } static Node newNode ( int data ) { Node temp = new Node ( ) ; temp . data = data ; temp . right = null ; temp . left = null ; return temp ; } static 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 ; } public static void main ( String [ ] args ) { 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 ) ; System . out . println ( " Finding ▁ K - th ▁ largest ▁ Node ▁ in ▁ BST ▁ : ▁ " + KthLargestUsingMorrisTraversal ( root , 2 ) . data ) ; } }