Find Kth smallest element in BST(Binary Search Tree)

Find Kth smallest element in Binary Search Tree.

Lets understand the problem statement correctly, What is the Input and the expected output.

Simple approach

STEP 1. Take a variable counter, which keep track of number of smallest element read till now.

STEP 2. Do In order traversal, instead of printing the node in in-order traversal, increment the
               counter till it matches K.

STEP 3. Check whether counter value is equal to K.

STEP 4. If YES, then current node is Kth smallest node and return it.
             If NO, then return -1 as indication that given 'K' is invalid.

Java Program to find Kth smallest element in BST using First Approach.

package tree;

public class FindKSmallestElementInBinarySearchTree {
 private Node rootNode;
 private static int counter;
 
 public static void main(String[] args) {
  new FindKSmallestElementInBinarySearchTree();
 }

 public FindKSmallestElementInBinarySearchTree() {
  addNode(rootNode, 40); 
  addNode(rootNode, 20); 
  addNode(rootNode, 60); 
  addNode(rootNode, 10); 
  addNode(rootNode, 30);
  addNode(rootNode, 50);
  addNode(rootNode, 70);

  printTreeInOrder(rootNode);

  Node kthSmallestNode = findKthSmallestItem(rootNode, 4);
  
  if(kthSmallestNode!=null){
   System.out.println("\nElement is :"+kthSmallestNode.getData());
  }else{
   System.out.println("\nElement not found");
  }
 }
 
 private Node findKthSmallestItem(Node rootNode, int k) {
  if(rootNode==null){
   return null;
  }

  Node node = findKthSmallestItem(rootNode.getLeft(), k);
  
  //If counter is not equal to K, then only increment the counter. 
  //Once counter is equal to K, it means we have found the desired smallest element and no need to increment further, 
  //Take the back up of the current node as it might be the Kth smallest element we are looking for.  
  if(counter != k){
   counter++;
   node = rootNode;
  }
  
  //This is the place where actual check is going to happen between counter and K, 
  //If counter matched K, it means we found the node and no need to find further so simply return the found node.
  if(counter == k){ 
   return node;
  }else{
   return findKthSmallestItem(rootNode.getRight(), k);
  }
 }
 
 private void printTreeInOrder(Node rootNode){
  if(rootNode==null)
   return;
  printTreeInOrder(rootNode.getLeft());
  System.out.print(rootNode.getData() + " ");
  printTreeInOrder(rootNode.getRight());
 }

 private void addNode(Node rootNode, int data){
  if(rootNode==null){
   Node temp1 = new Node(data);
   this.rootNode=temp1;
  }else{
   addNodeInProperPlace(rootNode, data);
  }
 }
 
 private void addNodeInProperPlace(Node rootNode, int data){ 
  if(data>rootNode.getData()){
   if(rootNode.getRight()!=null){
    addNode(rootNode.getRight(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setRight(temp1);
   }
  }else if(data<rootNode.getData()){
   if(rootNode.getLeft()!=null){
    addNode(rootNode.getLeft(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setLeft(temp1);
   }
  }
 }
}

package tree;

public class Node{
 
 private Node left;
 private Node right;
 private int data;
 
 public Node(int data){
  this.data=data;
 }

 public Node getLeft() {
  return left;
 }

 public void setLeft(Node left) {
  this.left = left;
 }

 public Node getRight() {
  return right;
 }

 public void setRight(Node right) {
  this.right = right;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }
}

Another approach of Finding K'th smallest item in BST

In this approach, we will use the Binary Search Tree property that,
1. Left sub tree of a Node contains elements smaller than Node.
2. Right sub tree of a Node contains elements higher than Node.

So, If we want to find Kth lowest element, we need to look at Left side of a Root Node first,
If Kth smallest is not found on Left side then only we will explore right side of Root Node.

Algorithm

STEP 1: Identify the children's of Left sub tree of Root Node. (store it in variable childCount).

STEP 2: If (childCount == K), we found the element.

STEP 3: If (childCount > K), then K is present some where in Left subtree of Root Node and
                we will explore left subtree of Root Node by moving one step towards Left of it.
                (rootNode -> left) and repeat the process.

STEP 4: If (childCount < K), then K is not present in Left subtree of Root Node and we will
                explore right subtree of Root Node by moving one step towards right of it.
                (rootNode -> right) and repeat the process.

While moving towards Right, we have to keep in mind that we already traversed
                (childCount) lowest element in BST and now we need to find (K - childCount) node in
right sub tree

      Repeat steps until node is not found.

Look at the below picture for better understanding of it.

Java Program to find Kth smallest element in BST using Second Approach.

package tree;

public class FindKSmallestElementInBinarySearchTree {
 private Node rootNode;

 public static void main(String[] args) {
  new FindKSmallestElementInBinarySearchTree();
 }

 public FindKSmallestElementInBinarySearchTree() {
  addNode(rootNode, 40); 
  addNode(rootNode, 20); 
  addNode(rootNode, 60); 
  addNode(rootNode, 10); 
  addNode(rootNode, 30);
  addNode(rootNode, 50);
  addNode(rootNode, 70);

  printTreeInOrder(rootNode);
  
  int kthSmallestElement = findKthSmallestItem(rootNode, 2);
  if(kthSmallestElement!=-1){
   System.out.println("Kth smallest node is :"+kthSmallestElement);
  }else{
   System.out.println("Kth smallest node is not found"); 
  }
 }

 private int findKthSmallestItem(Node rootNode, int k) {
  if(rootNode==null){
   return -1; //Indication that kth smallest is not found.
  }

  int childCount = getNodeCount(rootNode.getLeft());
  
  if(childCount+1==k){ // +1 for rootNode itself
   return rootNode.getData();
  
  }else if(childCount+1>=k){
   return findKthSmallestItem(rootNode.getLeft(), k);
  }else{
   return findKthSmallestItem(rootNode.getRight(), k - (childCount+1));
  }
 }
 
 private int getNodeCount(Node node){
  if(node == null){
   return 0;
  }
  int left = getNodeCount(node.getLeft());
  int right = getNodeCount(node.getRight());
  
  return 1 + left + right;
 }
 
 private void printTreeInOrder(Node rootNode){
  if(rootNode==null)
   return;
  printTreeInOrder(rootNode.getLeft());
  System.out.print(rootNode.getData() + " ");
  printTreeInOrder(rootNode.getRight());
 }

 private void addNode(Node rootNode, int data){
  if(rootNode==null){
   Node temp1 = new Node(data);
   this.rootNode=temp1;
  }else{
   addNodeInProperPlace(rootNode, data);
  }
 }
 private void addNodeInProperPlace(Node rootNode, int data){ 
  if(data>rootNode.getData()){
   if(rootNode.getRight()!=null){
    addNode(rootNode.getRight(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setRight(temp1);
   }
  }else if(data<rootNode.getData()){
   if(rootNode.getLeft()!=null){
    addNode(rootNode.getLeft(), data);
   }else{
    Node temp1 = new Node(data);
    rootNode.setLeft(temp1);
   }
  }
 }

}