Find k | A simple inorder traversal based Java program to find k - th smallest element in a BST . ; A BST node ; Recursive function to insert an key into BST ; If a node is inserted in left subtree , then lCount of this node is increased . For simplicity , we are assuming that all keys ( tried to be inserted ) are distinct . ; Function to find k 'th largest element in BST  Here count denotes the number of  nodes processed so far ; base case ; else search in right subtree ; main function
import java . io . * ; import java . util . * ; class Node { int data ; Node left , right ; int lCount ; Node ( int x ) { data = x ; left = right = null ; lCount = 0 ; } } class Gfg { public static Node insert ( Node root , int x ) { if ( root == null ) return new Node ( x ) ; if ( x < root . data ) { root . left = insert ( root . left , x ) ; root . lCount ++ ; } else if ( x > root . data ) root . right = insert ( root . right , x ) ; return root ; } public static Node kthSmallest ( Node root , int k ) { if ( root == null ) return null ; int count = root . lCount + 1 ; if ( count == k ) return root ; if ( count > k ) return kthSmallest ( root . left , k ) ; return kthSmallest ( root . right , k - count ) ; } public static void main ( String args [ ] ) { Node root = null ; int keys [ ] = { 20 , 8 , 22 , 4 , 12 , 10 , 14 } ; for ( int x : keys ) root = insert ( root , x ) ; int k = 4 ; Node res = kthSmallest ( root , k ) ; if ( res == null ) System . out . println ( " There ▁ are ▁ less ▁ " + " than ▁ k ▁ nodes ▁ in ▁ the ▁ BST " ) ; else System . out . println ( " K - th ▁ Smallest " + " ▁ Element ▁ is ▁ " + res . data ) ; } }