For people who are new to learning Data Structures and Algorithms, they often confuse Binary Trees for the Binary Search Trees, thinking they are essentially the same!

Well that is certainly not the case. The Binary Search Tree is implemented within every node of the Binary Tree in order to help with insertion, removal, lookup and faster traversal of the nodes of the tree structure.

This reflects that the contents (elements) of a Binary Tree or a Binary Search Tree are essentially the same with minute differences in their characteristics.

Today, we are going to learn how you can locate the Kth smallest element of a BST using different approaches and algorithms. More specifically, this blog provides a quick overview for finding the Kth smallest element in BST

 

What is a Binary Search Tree?

In order to understand the Binary Search Tree (also known as BST) in detail, we must have a look at what essentially are the components and characteristics of a Binary Tree.

Here are some of the basic components of a Binary Tree:

  • Within every Binary Tree data structure, you will find that each of them has a root node also referred to as the parent node that may contain a value or datatype.
  • The root node further extends to children nodes or it may limit itself. This can only be comprehended by looking at the structure of the tree.
  • These children nodes of a Binary Tree either limit themselves or they further branch out forming children nodes. This essentially means every children node of a Binary Tree can be a tree of its own.

Now, let's have a look at how the Binary Tree can be projected as a Binary Search Tree by simply adding the following two characteristics:

  • Every node of the Binary Tree is only allowed to have two children nodes.
  • Also, the values contained in the left part of the Binary Tree will always be lesser than the right subtree.

The main idea behind building a Binary Search Tree is to make sure that faster iteration and lookup can be performed within the program.

Also, forming a Binary Search Tree gives the programmers an edge to easily insert or delete programs using the Binary Search Algorithm.

Now, since we have learned quite a bit about manipulating data on a Binary Search Tree, similarly, in your coding interviews, you will find problems related to finding the Kth smallest element in BST

Since this is one of the most commonly asked questions for the technical and coding interviews, we would definitely recommend checking out the following section for the proper approaches and algorithms for solving this problem statement.

 

How to find the Kth Smallest Element in a Binary Search Tree? 

Before learning how to find Kth smallest element in BST, let us discuss what does the Kth element mean in terms of a Binary Search Tree.

Essentially, the Kth element is the smallest node containing a minimum value. 

Usually in a problem statement of this sort, you will find the output for the Kth element given for a Binary Search Tree that you will have to print later by implementing suitable approaches in a program.

Meanwhile, check out the problem statement for finding the kth smallest element in a BST.

 

Problem Statement

You have been given the root of a Binary Tree with k as its input. Your task is finding the Kth smallest element of the BST. 

For instance, 

Check out the following diagram of a BST:

                                     20

 

  1.                         22

 

  1.               12

 

  1.           14

 

Now, in the context of the above Binary Search Tree, if the given value of k equals 3, then the resulting output would be 10.

Now, since we are on the subject of Binary Trees, we would naturally use one of the single tree traversal methods for solving this problem statement. In this context, we will be employing the In Order Traversal method.

 

Method 1: Using the In-order Tree Traversal

The In-Order Traversal in a BST is performed using the recursive function. But, did you know that you can also apply the recursive approach for find all anagrams in a string

With that in mind, let us elaborate further on the in-order Binary Tree Traversal Approach. This mechanism essentially follows the root tree traversal format. Starting from the left part of the BST, heading towards the nodes of the right subtree and finally visiting the root of the tree.

Now, in order to find Kth smallest element in BST, we will be applying the following algorithm for In-Order Traversal:

  • Start by traversing the tree in-orde while keeping track of the nodes that have been previously visited.
  • Once the value of the nodes reaches the k limit, you can print the nodes to end the traversal.

Time Complexity for this approach:

The time complexity for this approach would be O(h) where h is being used as a derivative for the height of the tree.

 

Method 2: Augmenting the Tree Data Structure by challenging the O(h) time complexity and auxiliary space 

The intention of using this approach is maintaining a rank for every node of the Binary Tree. 

While we are building the tree, we will be keeping track of all the nodes contained in the left subtree.

Now, since we have to find the Kth smallest element of the given BST, we need to maintain the value of elements contained in the left subtree for every node.

Here's how the algorithm for augmenting the data structure would work:

  • We have to apply the following formula in order to locate the Kth smallest element in the Binary Tree:

K= lCount + 1, here the root of the tree will be the Kth node.

  • We will continue this search in a recursive format until the Kth smallest element in the left subtree is found.
  • Locate elements within the left subtree of the given BST.

Time Complexity for this approach:

O(h), here h is representative of the height of the tree.

 

Wrapping Up

Reducing the time and space complexity of any given program demands losing the recursive approach and implementing the iterative methods.

Ultimately, when you are in an interview situation, finding the solutions to coding problems is not enough until you work on reducing the time complexity.

Our blogs can help you learn how to manage the time complexity for the recursive approach and teach you how to implement it for flattening linked lists, merging sorted arrays or find all anagrams in a string.