# Solution For Kth Smallest Element In A Bst

Problem Statement:

Given the root of a binary search tree, and an integer k, return the kth (1-indexed) smallest element in the tree.

Example 1:

Input: root = [3,1,4,null,2], k = 1

Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

Output: 3

Constraints:

The number of nodes in the tree is n.

1 <= k <= n <= 104

0 <= Node.val <= 104

Solution:

Approach 1: Inorder Traversal of BST

One of the simplest and most intuitive solutions for this problem is to traverse the tree in an inorder fashion. In an inorder traversal of BST, the elements are sorted in ascending order. So, we can traverse the tree in inorder, and maintain a count of the number of nodes that we have visited so far. Once the count becomes equal to k, we have reached the kth smallest element.

Algorithm:

1. Traverse the BST in inorder fashion.
2. While traversing, do the following:
a. When we visit a node, increment the counter by 1.
b. If the counter becomes equal to k, return the value of the current node.
3. If we have traversed the entire tree and haven’t found the kth smallest element, return -1.

Time Complexity:

O(n) – We have to traverse the entire tree.

Space Complexity:

O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

Approach 2: Finding the kth Smallest Element Using Binary Search

Another approach to solve this problem is to make use of binary search. We can perform a binary search on the range of values that are present in the BST. We can start with the smallest value in the BST and the largest value in the BST, and find the middle element. We can then find the number of nodes that are smaller than or equal to this middle element. If this number is less than k, we can discard the left half of the range, and repeat the same process on the right half. If this number is greater than or equal to k, we can discard the right half of the range, and repeat the same process on the left half. We can continue performing the binary search until we find the kth smallest element.

Algorithm:

1. Initialize l and r to the minimum and maximum values in the BST, respectively.
2. While l <= r, do the following:
a. Set mid to (l+r)/2.
b. Set cnt to the number of nodes that are smaller than or equal to mid.
c. If cnt < k, set l to mid+1.
d. If cnt >= k, set r to mid-1.
3. Return l.

Time Complexity:

O(n*log(max_value-min_value)) – We have to perform binary search, which has a time complexity of O(log(max_value-min_value)), where max_value and min_value are the maximum and minimum values in the BST, respectively. We also have to find the number of nodes that are smaller than or equal to a given value, which can be done in O(n) time.

Space Complexity:

O(h) – We are making use of the call stack, which can grow up to h levels, where h is the height of the tree.

## Step by Step Implementation For Kth Smallest Element In A Bst

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
//inorder traversal of a BST gives us the elements in sorted order
List list = new ArrayList<>();
inorder(root, list);
return list.get(k-1);
}

public void inorder(TreeNode root, List list){
if(root == null) return;
inorder(root.left, list);
inorder(root.right, list);
}
}```
```def kthSmallest(self, root: TreeNode, k: int) -> int:

# Initialize an empty stack
stack = []

# Push the root node to the stack
stack.append(root)

# Initialize a count variable to keep track of nodes visited
count = 0

# Loop until stack is empty
while stack:

# Pop the top node from the stack
node = stack.pop()

# If the node has a right child, push it to the stack
if node.right:
stack.append(node.right)

# If the node doesn't have a left child, it is a leaf node
# so increment the count and check if it is the kth smallest node
if not node.left:
count += 1
if count == k:
return node.val

# If the node has a left child, push it to the stack
if node.left:
stack.append(node.left)```
```/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
// create an empty array to store all node values
const nums = [];
// traverse the tree using in-order traversal
// this will store the node values in ascending order
inOrder(root);
// return the kth element in the array
return nums[k - 1];

function inOrder(node) {
// if the node is null, return
if (!node) return;
// recursively call inOrder on the left child
inOrder(node.left);
// push the node's value into the array
nums.push(node.val);
// recursively call inOrder on the right child
inOrder(node.right);
}
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
int count = 0;
int result = 0;

inorder(root, k, count, result);

return result;
}

void inorder(TreeNode* root, int k, int& count, int& result) {
if (root == nullptr) {
return;
}

inorder(root->left, k, count, result);
count++;
if (count == k) {
result = root->val;
return;
}
inorder(root->right, k, count, result);
}
};```
```public int KthSmallest(TreeNode root, int k) {
// Base Case
if (root == null) {
return 0;
}

// Create a stack to do iterative inorder traversal
Stack st = new Stack();

// Initialize current node as root
TreeNode curr = root;

// Traverse the tree
while (curr != null || st.Count > 0) {

/* Reach the left most TreeNode of the
curr TreeNode */
while (curr !=  null) {
st.Push(curr);
curr = curr.left;
}

/* Current must be NULL at this point */
curr = st.Pop();

// Decrement count by 1
k--;

// If the count becomes zero, return current
if (k == 0) {
return curr.val;
}

/* Else go to the right subtree */
curr = curr.right;
}

// If k is still greater than 0, then it is not
// possible to find kth smallest element
return -1;
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]