Kth Smallest element in a Perfect Binary Search Tree | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; Node * left , * right ; } ; 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 ; } bool KSmallestPerfectBST ( Node * root , int k , int treeSize , int & kth_smallest ) { 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 , kth_smallest ) ; } int newK = k - median_loc ; return KSmallestPerfectBST ( root -> right , newK , newTreeSize , kth_smallest ) ; } 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 ) ; 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 ; int ans = -1 ; if ( KSmallestPerfectBST ( root , k , n , ans ) ) { cout << ans << " ▁ " ; } return 0 ; }