Kth Smallest element in a Perfect Binary Search Tree | Java program to find K - th smallest element in a perfect BST ; A BST node ; 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 ; Recur down the left subtree for smaller values ; Recur down the right subtree for smaller values ; Return the ( unchanged ) node pointer ; FUnction to find Kth Smallest element in a perfect BST ; Find the median ( division operation is floored ) ; If the element is at the median ; calculate the number of nodes in the right and left sub - trees ( division operation is floored ) ; If median is located higher ; If median is located lower ; Driver Code ; Let us create following BST 50 / \ 30 70 / \ / \ 20 40 60 80 / \ / \ / \ / \ 14 25 35 45 55 65 75 85 ; Function call
import java . util . * ; class GFG { static class Node { int key ; Node left , right ; } ; static int kth_smallest ; public static Node newNode ( int item ) { Node temp = new Node ( ) ; temp . key = item ; temp . left = temp . right = null ; return temp ; } static 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 ; } static boolean KSmallestPerfectBST ( Node root , int k , int treeSize ) { if ( root == null ) return false ; int median_loc = ( treeSize / 2 ) + 1 ; if ( k == median_loc ) { kth_smallest = root . key ; return true ; } int newTreeSize = treeSize / 2 ; if ( k < median_loc ) { return KSmallestPerfectBST ( root . left , k , newTreeSize ) ; } int newK = k - median_loc ; return KSmallestPerfectBST ( root . right , newK , newTreeSize ) ; } public static void main ( String [ ] args ) { 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 ) ; insert ( root , 14 ) ; insert ( root , 25 ) ; insert ( root , 35 ) ; insert ( root , 45 ) ; insert ( root , 55 ) ; insert ( root , 65 ) ; insert ( root , 75 ) ; insert ( root , 85 ) ; int n = 15 , k = 5 ; if ( KSmallestPerfectBST ( root , k , n ) ) { System . out . print ( kth_smallest + " ▁ " ) ; } } }