Find K smallest element in binary search tree

Given a binary search tree (bst), we would like to find out K smallest element in BST.
Traverse the binary search tree using depth first search (DFS) recursive algorithm.
Perform InOrder binary tree traversal to find smallest K smallest element.
- InOrder tree traversal prints elements in sorted order.
- We can find out K smallest from sorted order result.
We will use of properties of binary search tree to find k smallest element.

K smallest bst dfs — Fig 1: K smallest element BST

Example: find Kth smallest element in binary search tree.

Traverse the binary tree using inorder tree traversal algorithm.
The inOrder traversal of binary tree is as follows:
1. Visit left child
2. Visit current node or parent node
3. Visit right child

inorder traversal bst — Fig 2: Inorder traversal of BST

The Inorder traversal of binary search tree is:
25 50 75 100 120 125 140 150 160 175 190

K value	Output value
1	25
3	75
5	120
8	150

Algorithm to find K Smallest Element in BST (DFS/recursive).

Pass K representing the element (Kth smallest element in BST)
Array representing the number of element visited [int arr[] = {0}]
- We have wrapped the integer to array
- Pass integer as array object.
  - So that we can use its reference in recursive call
- In recursive call keeping track of this integer
- We have used it to compare with K
Perform InOrder tree traversal (DFS traversal)
Whenever we found arr[0] == K
- We found the Kth element
- Start returning from recursive call
At the end of loop, we will get the K Smallest element in BST.
Time Complexity: O(n)

Program – find K smallest element in binary search tree (recursive algorithm)

1.) KSmallestElement Class:

KSmallestElement class performs Inorder traversal of binary search tree to find out Kth smallest element.

package org.learn.Question;
 
import org.learn.PrepareTree.Node;
 
public class KSmallestElement {
    public static Node kSmallestElement(Node root, int k, int[] iElement) {
        if(null == root) {
            return root;
        }
         
        Node left = kSmallestElement(root.left, k, iElement );
        if(null != left) {
            return left;
        }
         
        iElement[0] ++;
        if(iElement[0] == k) {
            return root; 
        }
        return kSmallestElement(root.right,k, iElement);
    }
     
}

2.) App Class:

We are creating the binary search tree in main method.
We will invoke method of KSmallestElement class to find out Kth smallest element in a binary search.

package org.learn.Client;
 
import org.learn.PrepareTree.Node;
import org.learn.Question.KSmallestElement;
 
public class App {
    public static void main( String[] args) {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
              
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;
       G.left = J;
       G.right = K;
          
       int arr[] = {0};
       int k = 3;
       Node element = KSmallestElement.kSmallestElement(A,k,arr);
       if(null != element)
           System.out.printf("Smallest element K =
                                   %d is %d ",k,element.data);
       else {
           System.out.printf("No element found for K = %d",k);
       }
       arr[0] = 0;
       k = 5;
       element = KSmallestElement.kSmallestElement(A,k,arr);
       if(null != element)
           System.out.printf("\nSmallest element K = 
                                 %d is %d ",k,element.data);
       else {
           System.out.printf("No element found for K = %d",k);
       }        
    }
}

3.) Node Class:

Node class representing the nodes of a binary tree.

package org.learn.PrepareTree;
 
public class Node {
    public int data;
    public Node left;
    public Node right;
 
    public Node(int num) {
        this.data = num;
        this.left = null;
        this.right = null;
    }
 
    public Node() {
        this.left = null;
        this.right = null;
    }
    public static Node createNode(int number) {
        return new Node(number);
    }
}

Output – K smallest element in binary search tree (depth first search)

Smallest element K = 3 is 75
Smallest element K = 5 is 120

Find K smallest element in binary search tree (BST) – DFS / example

Example: find Kth smallest element in binary search tree.

Algorithm to find K Smallest Element in BST (DFS/recursive).

Program – find K smallest element in binary search tree (recursive algorithm)

1.) KSmallestElement Class:

2.) App Class:

3.) Node Class:

Output – K smallest element in binary search tree (depth first search)

Download Code – K Smallest Element in Binary serach tree – DFS

Example: find Kth smallest element in binary search tree.

Algorithm to find K Smallest Element in BST (DFS/recursive).

Program – find K smallest element in binary search tree (recursive algorithm)

1.) KSmallestElement Class:

2.) App Class:

3.) Node Class:

Output – K smallest element in binary search tree (depth first search)

You may also like: