How to find Kth Smallest Element in a Binary Search Tree? [Solved]

Hello guys, I have been sharing binary search tree-based coding interview questions for quite some time. In the last article, we looked at how to find the maximum sum level in a given binary tree, and in this article, we will find the kth smallest number in a given binary tree like the 5th smallest or 3rd smallest number. Before we find the kth smallest in a Binary search tree, We need to understand the binary search tree. A Binary tree is a data structure in which each node can have at most two children. That is, each node in the binary tree will have data, left child and right child. The first node of the tree is called the Root.

There are some important things to note when determining is if a tree is a binary tree or not, which are :

• All data in the nodes of the left sub-tree are lesser than the right.
• In the Children nodes, All data on the left are lesser than the right.
• All data in the nodes of the left sub-tree is lesser than the root
• All data in the nodes of the right sub-tree is greater than the root.

So, with all these bullet points you can determine if a tree is a binary tree or not. We shall we do a task to find out for better understanding.

In the following binary search tree diagram, The root node is node 5 as you can see, And it has two Children, node 3 and node 6, left and right respectively. Node 3 also has two children nodes 2 and 4. Node 6 has just one child, node 7, Nodes 2,4, and 7 are called leaves because they do not have children.

Fig 1.0: finding the kth element in the binary search tree

I hope the image above communicates more to you?, let us move to the code implementation

Now, we shall be finding the kth smallest element in the binary tree, if you do not understand what and how a binary tree works you may need to check that first, for better understanding. Looking for the smallest element requires that we traverse through the entire tree both left sub-tree Let’s say for instance,

If you sort an array from smallest to largest, assuming our k is 3, the kth smallest element is the 3rd element in the sorted array. and if k still remains 3 as we find the largest in the array, The kth largest element is the 3rd element from the end in the sorted array.

[1, 6, 7, 8, 10, 19, 19, 20, 23, 24]


The smallest element is 1, the second smallest is 6, and so on. So the kth smallest is the kth element from the left. Similarly, 24 is the largest, 23 is the second-largest, and so on, so the kth largest element is the kth element from the right. So if k = 5, 19 is our Kth largest element(I.e, the fifth-largest element).

Java Program to find the Kth Smallest element in a binary search tree

Now let’s write some code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

public class KthSmallest { // function to find k-th largest element static int findKthSmallest(ArrayList < ArrayList < Integer >> list, int k) { int n = list.size(); if (k > n * n) return -1; // smallest element is the first element of the matrix if (k == 1) return list.get(0).get(0); // define array and push contents of the matrix into it ArrayList < Integer > arr = new ArrayList < Integer > (); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) arr.add(list.get(i).get(j)); // sort the array and obtain k-th smallest element Collections.sort(arr); return arr.get(k - 1); } public static void main(String[] args) { ArrayList < ArrayList < Integer >> mat = new ArrayList < ArrayList < Integer >> (); list.add(new ArrayList < Integer > (Arrays.asList(11, 21, 31, 41))); list.add(new ArrayList < Integer > (Arrays.asList(16, 26, 36, 46))); list.add(new ArrayList < Integer > (Arrays.asList(25, 30, 38, 49))); list.add(new ArrayList < Integer > (Arrays.asList(33, 34, 40, 50))); int k = 3; int kthsmall = findKthSmallest(list, k); if (kthsmall == -1) System.out.println(k + "rd " + "smallest element doesn't exist."); else System.out.println((k + "rd " + " smallest element = " + kthsmall); } }

Class declaration in line 3, and line 6 the method to find the smallest kth element was declared with a list of integer type as parameter with the name list and another parameter of type int, Note that: the list takes in a list of integer. The size was gotten and stored in variable n of type int in line 9. 

There were two if conditions that follows. First, if parameter k is greater than the size multiplied by itself (I.e n *n) it should return -1. 

Second, if parameter k is equal to 1 it should return the first item of the list in the array list. In line 18, the Arraylist of type Integer was created and instantiated to the new Arraylist followed by two different loops because we are working with two lists. 

So as it traverses it should get the first element of the first list and add it to the list we just created. After, method sort(an inbuilt method in java) was called to sort the list. And it returned the k-1 that was gotten.

Remember the conditions, anyone that meets the condition works.

The main method starts from line 28, Elements were being added to the list, and k was initialized to 3. after that, the method "find kth smallest" was called and saved into the variable "kthSmallest". So, if kthSmallest is equal to -1 it prints 3rd element does not exist, if it does it prints it out.

OUTPUT:

3th smallest element = 21

That's all about how to find the kth smallest element in a given binary search tree in Java. You can also use this technique to find the third smallest or fifth smallest number in a binary search tree and you can also improvise it to find the kth largest element in a given binary search tree. In fact, I have an exercise for you. can you find the 5th largest number in this binary search tree?

And, if you like to practice more, here are more coding interview questions with solutions

• Top 50 Java Programs from Coding Interviews (see here)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• How to check if a String is a Palindrome in Java? [solution]
• How to find the missing number in a sorted array in Java? [answer]
• 10 Algorithms Books Every Programmer Should Read (books)
• How to remove an element from the array without using a third-party library (check here)
• How to implement the Quicksort algorithm in Java? (solution)
• 5 Books to learn data structure and algorithms in Java? (books)
• How to print the Fibonacci series in Java without using Recursion? [solution]
• 10 Algorithm books Every Programmer Should Read (list)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• How to check if an integer is a power of two without using division or modulo operator?[hint]
• How to find all permutations of String in Java? [solution]
• Top 20 String coding interview questions (see here)
• How to find the largest and smallest number in an array in Java (read here)
• How to find two maximum numbers on an integer array in Java (check here)

If you have any suggestions to make this algorithm better, feel free to suggest. The interviewer loves people who come up with their own algorithms or give some touch to popular algorithms. Also if you like this question, do comment and let us know so that we can create more of such articles. 

P. S. - If you want to improve your data structure and algorithms skills and you need resources then you can also take a look at my list of best data structure and algorithm courses for Java developers. It contains some best online courses from Udemy, Coursera, edX, and other resources for Java developers.