Kth smallest/largest node in a BST

Problem Statement :

    Find the Kth Smallest and Largest node in the given BST

Solution:

1. To find the kth smallest Node

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

static int count=0; public void KthSmallest(Node root ,int k) { if(root == null) return ; KthSmallest(root.left , k) ; if(++count == k) { System.out.println( k+ " th smallest element is : " + root.data); return ; } KthSmallest(root.right , k); }

2. To find the kth largest Node

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

//----- kth largest element in BST ---- static int count=0; public void KthLargest(Node root ,int k) { if(root == null) return ; KthLargest(root.right , k) ; if(++count == k) { System.out.println( k+ " th largest element is : " + root.data); return ; } KthLargest(root.left , k); }

Note: Ensure that size of the tree is greater than the value of k passed.

To calculate size of the tree

1 2 3 4 5 6 7 8

//-------------------Size of Tree-------------------------- public int size(Node root) { if(root==null) return 0; else return (size(root.left)+1+size(root.right)); }