Given the root of a Binary Search Tree (BST) and a positive integer k, find the kth smallest element in the Binary Search Tree.
Example:
Input: k = 3
Output: 10
Explanation: The inorder traversal of given BST is [4, 8, 10, 12, 14, 20, 22] and its 3rd smallest element is 10.
Try it on GfG Practice
Table of Content
[Expected Approach] Using In-Order traversal - O(k) Time and O(h) Space
The idea is to traverse the binary search tree using in-order traversal while maintaining the count of nodes traversed. If the node count becomes equal to k, then return the node.
//Driver Code Starts
#include <iostream>
using namespace std;
// Node Structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int x) {
data = x;
left = nullptr;
right = nullptr;
}
};
//Driver Code Ends
// Recursive function for inorder traversal of the tree and
// find its kth smallest value
int kthSmallestRecur(Node* root, int &cnt, int k) {
if (root == nullptr) return -1;
int left = kthSmallestRecur(root->left, cnt, k);
// If kth smallest is found in left
// subtree, then return it
if (left != -1) return left;
cnt++;
// If curr node is kth smallest,
// return it
if (cnt == k) return root->data;
// Else process the right subtree
// and return its value
int right = kthSmallestRecur(root->right, cnt, k);
return right;
}
// Function to find kth Smallest
int kthSmallest(Node* root, int k) {
int cnt = 0;
return kthSmallestRecur(root, cnt, k);
}
//Driver Code Starts
int main() {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node* root = new Node(20);
root->left = new Node(8);
root->right = new Node(22);
root->left->left = new Node(4);
root->left->right = new Node(12);
root->left->right->left = new Node(10);
root->left->right->right = new Node(14);
int k = 3;
cout << kthSmallest(root, k) << endl;
return 0;
}
//Driver Code Ends
// Driver Code Starts
#include <stdio.h>
#include <stdlib.h>
// Node Structure
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Function to create a new Node
Node* newNode(int x) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Recursive function for inorder traversal of the tree and
// find its kth smallest value
int kthSmallestRecur(Node* root, int *cnt, int k) {
if (root == NULL)
return -1;
int left = kthSmallestRecur(root->left, cnt, k);
// If kth smallest is found in left subtree, return it
if (left != -1)
return left;
(*cnt)++;
// If current node is kth smallest, return it
if (*cnt == k)
return root->data;
// Else process the right subtree and return its value
return kthSmallestRecur(root->right, cnt, k);
}
// Function to find kth Smallest
int kthSmallest(Node* root, int k) {
int cnt = 0;
return kthSmallestRecur(root, &cnt, k);
}
// Driver Code Starts
int main() {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node* root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int k = 3;
printf("%d\n", kthSmallest(root, k));
return 0;
}
// Driver Code Ends
//Driver Code Starts
// Node Structure
class Node {
int data;
Node left, right;
Node(int x) {
data = x;
left = null;
right = null;
}
}
class GFG {
//Driver Code Ends
// Recursive function for inorder traversal of the tree and
// find its kth smallest value
static int kthSmallestRecur(Node root, int[] cnt, int k) {
if (root == null) return -1;
int left = kthSmallestRecur(root.left, cnt, k);
// If kth smallest is found in left
// subtree, then return it
if (left != -1) return left;
cnt[0]++;
// If curr node is kth smallest,
// return it
if (cnt[0] == k) return root.data;
// Else process the right subtree
// and return its value
int right = kthSmallestRecur(root.right, cnt, k);
return right;
}
// Function to find kth Smallest
static int kthSmallest(Node root, int k) {
int[] cnt = {0};
return kthSmallestRecur(root, cnt, k);
}
//Driver Code Starts
public static void main(String[] args) {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
int k = 3;
System.out.println(kthSmallest(root, k));
}
}
//Driver Code Ends
#Driver Code Starts
# Node Structure
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
#Driver Code Ends
# Recursive function for inorder traversal of the tree and
# find its kth smallest value
def kthSmallestRecur(root, cnt, k):
if root is None:
return -1
left = kthSmallestRecur(root.left, cnt, k)
# If kth smallest is found in left
# subtree, then return it
if left != -1:
return left
cnt[0] += 1
# If curr node is kth smallest,
# return it
if cnt[0] == k:
return root.data
# Else process the right subtree
# and return its value
right = kthSmallestRecur(root.right, cnt, k)
return right
# Function to find kth Smallest
def kthSmallest(root, k):
cnt = [0]
return kthSmallestRecur(root, cnt, k)
#Driver Code Starts
if __name__ == "__main__":
# Binary search tree
# 20
# / \
# 8 22
# / \
# 4 12
# / \
# 10 14
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
k = 3
print(kthSmallest(root, k))
#Driver Code Ends
//Driver Code Starts
using System;
// Node Structure
class Node {
public int data;
public Node left, right;
public Node(int x) {
data = x;
left = null;
right = null;
}
}
class GFG {
//Driver Code Ends
// Recursive function for inorder traversal of the tree and
// find its kth smallest value
static int kthSmallestRecur(Node root, ref int cnt, int k) {
if (root == null) return -1;
int left = kthSmallestRecur(root.left, ref cnt, k);
// If kth smallest is found in left
// subtree, then return it
if (left != -1) return left;
cnt++;
// If curr node is kth smallest,
// return it
if (cnt == k) return root.data;
// Else process the right subtree
// and return its value
int right = kthSmallestRecur(root.right, ref cnt, k);
return right;
}
// Function to find kth Smallest
static int kthSmallest(Node root, int k) {
int cnt = 0;
return kthSmallestRecur(root, ref cnt, k);
}
//Driver Code Starts
static void Main(string[] args) {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
int k = 3;
Console.WriteLine(kthSmallest(root, k));
}
}
//Driver Code Ends
//Driver Code Starts
// Node Structure
class Node {
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
//Driver Code Ends
// Recursive function for inorder traversal of the tree
// and find its kth smallest value
function kthSmallestRecur(root, cnt, k) {
if (root === null) return -1;
let left = kthSmallestRecur(root.left, cnt, k);
// If kth smallest is found in left
// subtree, then return it
if (left !== -1) return left;
cnt[0]++;
// If curr node is kth smallest,
// return it
if (cnt[0] === k) return root.data;
// Else process the right subtree
// and return its value
let right = kthSmallestRecur(root.right, cnt, k);
return right;
}
// Function to find kth Smallest
function kthSmallest(root, k) {
let cnt = [0];
return kthSmallestRecur(root, cnt, k);
}
//Driver Code Starts
// Driver Code
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
const root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
const k = 3;
console.log(kthSmallest(root, k));
//Driver Code Ends
Output
10
[Expected Approach] Using Morris Inorder Traversal - O(n) Time and O(1) Space
The idea is to perform an inorder traversal of the given Binary Search Tree using the Morris Traversal algorithm.
We can do the morris traversal and count nodes until we reach a count of k, and at that iteration, we return the current node.
//Driver Code Starts
#include <iostream>
using namespace std;
// Node Structure
class Node {
public:
int data;
Node* left;
Node* right;
Node(int x) {
data = x;
left = nullptr;
right = nullptr;
}
};
//Driver Code Ends
// Function to find kth Smallest
int kthSmallest(Node* root, int k) {
int count = 0;
Node* curr = root;
while (curr != nullptr) {
if (curr->left == nullptr) {
count++;
if (count == k) return curr->data;
curr = curr->right;
} else {
// Find the inorder predecessor of curr
Node* prev = curr->left;
while (prev->right != nullptr && prev->right != curr) {
prev = prev->right;
}
// Make curr the right child of its inorder predecessor
if (prev->right == nullptr) {
prev->right = curr;
curr = curr->left;
} else {
count++;
if (count == k) return curr->data;
// Revert the changes made in the tree structure
prev->right = nullptr;
curr = curr->right;
}
}
}
return -1;
}
//Driver Code Starts
int main() {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node* root = new Node(20);
root->left = new Node(8);
root->right = new Node(22);
root->left->left = new Node(4);
root->left->right = new Node(12);
root->left->right->left = new Node(10);
root->left->right->right = new Node(14);
int k = 3;
cout << kthSmallest(root, k) << endl;
}
//Driver Code Ends
#include <stdio.h>
#include <stdlib.h>
// Node Structure
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;
// Function to create a new Node
Node* newNode(int x) {
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp;
}
// Function to find kth Smallest using Morris Traversal
int kthSmallest(Node* root, int k) {
int count = 0;
Node* curr = root;
while (curr != NULL) {
if (curr->left == NULL) {
count++;
if (count == k) return curr->data;
curr = curr->right;
}
else {
// Find inorder predecessor
Node* prev = curr->left;
while (prev->right != NULL && prev->right != curr) {
prev = prev->right;
}
// Threading: make curr right child of its inorder predecessor
if (prev->right == NULL) {
prev->right = curr;
curr = curr->left;
}
else {
// Revert the threading
prev->right = NULL;
count++;
if (count == k) return curr->data;
curr = curr->right;
}
}
}
return -1;
}
int main() {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node* root = newNode(20);
root->left = newNode(8);
root->right = newNode(22);
root->left->left = newNode(4);
root->left->right = newNode(12);
root->left->right->left = newNode(10);
root->left->right->right = newNode(14);
int k = 3;
printf("%d\n", kthSmallest(root, k));
return 0;
}
//Driver Code Starts
// Node Structure
class Node {
int data;
Node left, right;
Node(int x) {
data = x;
left = null;
right = null;
}
}
class GFG {
//Driver Code Ends
// Function to find kth Smallest
static int kthSmallest(Node root, int k) {
int count = 0;
Node curr = root;
int nodes = 0;
while (curr != null) {
if (curr.left == null) {
count++;
if( count == k ) return curr.data;
curr = curr.right;
}
else {
// Find the inorder predecessor of curr
Node prev = curr.left;
while (prev.right != null &&
prev.right != curr) {
prev = prev.right;
}
// Make curr the right child of its inorder predecessor
if (prev.right == null) {
prev.right = curr;
curr = curr.left;
}
else {
count++;
if( count == k ) return curr.data;
// Revert the changes made in the tree structure
prev.right = null;
curr = curr.right;
}
}
}
return -1;
}
//Driver Code Starts
public static void main(String[] args) {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
int k = 3;
System.out.println(kthSmallest(root, k));
}
}
//Driver Code Ends
#Driver Code Starts
# Node Structure
class Node:
def __init__(self, x):
self.data = x
self.left = None
self.right = None
#Driver Code Ends
# Function to find kth Smallest
def kthSmallest(root, k):
count = 0
curr = root
while curr is not None:
if curr.left is None:
count += 1
if count == k:
return curr.data
curr = curr.right
else:
# Find the inorder predecessor of curr
prev = curr.left
while prev.right is not None and prev.right != curr:
prev = prev.right
# Make curr the right child of its inorder predecessor
if prev.right is None:
prev.right = curr
curr = curr.left
else:
count += 1
if count == k:
return curr.data
# Revert the changes made in the tree structure
prev.right = None
curr = curr.right
return -1
#Driver Code Starts
if __name__ == "__main__":
# Binary search tree
# 20
# / \
# 8 22
# / \
# 4 12
# / \
# 10 14
root = Node(20)
root.left = Node(8)
root.right = Node(22)
root.left.left = Node(4)
root.left.right = Node(12)
root.left.right.left = Node(10)
root.left.right.right = Node(14)
k = 3
print(kthSmallest(root, k))
#Driver Code Ends
//Driver Code Starts
using System;
// Node Structure
class Node {
public int data;
public Node left, right;
public Node(int x) {
data = x;
left = null;
right = null;
}
}
class GFG {
//Driver Code Ends
// Function to find kth Smallest
static int kthSmallest(Node root, int k) {
int count = 0;
Node curr = root;
while (curr != null) {
if (curr.left == null) {
count++;
if (count == k) return curr.data;
curr = curr.right;
}
else {
// Find the inorder predecessor of curr
Node prev = curr.left;
while (prev.right != null && prev.right != curr) {
prev = prev.right;
}
// Make curr the right child of its inorder predecessor
if (prev.right == null) {
prev.right = curr;
curr = curr.left;
}
else {
count++;
if (count == k) return curr.data;
// Revert the changes made in the tree structure
prev.right = null;
curr = curr.right;
}
}
}
return -1;
}
//Driver Code Starts
public static void Main(string[] args) {
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
Node root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
int k = 3;
Console.WriteLine(kthSmallest(root, k));
}
}
//Driver Code Ends
//Driver Code Starts
// Node Structure
class Node {
constructor(x) {
this.data = x;
this.left = null;
this.right = null;
}
}
//Driver Code Ends
// Function to find kth Smallest
function kthSmallest(root, k) {
let count = 0;
let curr = root;
while (curr !== null) {
if (curr.left === null) {
count++;
if (count === k) return curr.data;
curr = curr.right;
} else {
// Find the inorder predecessor of curr
let prev = curr.left;
while (prev.right !== null && prev.right !== curr) {
prev = prev.right;
}
// Make curr the right child of its inorder predecessor
if (prev.right === null) {
prev.right = curr;
curr = curr.left;
} else {
count++;
if (count === k) return curr.data;
// Revert the changes made in the tree structure
prev.right = null;
curr = curr.right;
}
}
}
return -1;
}
//Driver Code Starts
// Driver code
// Binary search tree
// 20
// / \
// 8 22
// / \
// 4 12
// / \
// 10 14
let root = new Node(20);
root.left = new Node(8);
root.right = new Node(22);
root.left.left = new Node(4);
root.left.right = new Node(12);
root.left.right.left = new Node(10);
root.left.right.right = new Node(14);
let k = 3;
console.log(kthSmallest(root, k));
//Driver Code Ends
Output
10