K'th smallest element in BST using O(1) Extra Space

Last Updated : 23 Jul, 2025

Given a Binary Search Tree (BST) and a positive integer k, find the k’th 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.

Approach:

The idea is to perform in-order traversal using Morris Traversal Algorithm while maintaining the count of nodes visited. When count becomes equal to k, return the node value.

C++

//Driver Code Starts // C++ program to find kth smallest value in BST #include <iostream> using namespace std; 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 element in a BST. int kthSmallest(Node* root, int k) {  int cnt = 0;    Node* curr = root;  while (curr != nullptr) {    // If left child is null, check   // curr node and move to right node.  if (curr->left == nullptr) {  cnt++;    // If curr is kth smallest node   if (cnt == k) return curr->data;    curr = curr->right;  }  else {  // Find the inorder predecessor of curr  Node* pre = curr->left;  while (pre->right != nullptr  && pre->right != curr)  pre = pre->right;  // Make curr as the right child of its  // inorder predecessor and move to   // left node.  if (pre->right == nullptr) {  pre->right = curr;  curr = curr->left;  }  // Revert the changes made in the 'if' part to  // restore the original tree i.e., fix the right  // child of predecessor  else {  pre->right = nullptr;    cnt++;  if (cnt == k) return curr->data;    curr = curr->right;  }  }  }    // If k is greater than size of   // BST, return -1.  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;  return 0; } //Driver Code Ends

//Driver Code Starts // C program to find kth smallest value in BST #include <stdio.h> #include <stdlib.h> struct Node {  int data;  struct Node* left;  struct Node* right; }; //Driver Code Ends   // Function to find kth smallest element in a BST. int kthSmallest(struct Node* root, int k) {  int cnt = 0;    struct Node* curr = root;  while (curr != NULL) {    // if left child is null, check   // curr node and move to right node.  if (curr->left == NULL) {  cnt++;    // If curr is kth smallest node   if (cnt == k) return curr->data;    curr = curr->right;  }  else {  // Find the inorder predecessor of curr  struct Node* pre = curr->left;  while (pre->right != NULL && pre->right != curr)  pre = pre->right;  // Make curr as the right child of its  // inorder predecessor and move to   // left node.  if (pre->right == NULL) {  pre->right = curr;  curr = curr->left;  }    // Revert the changes made in the 'if' part to  // restore the original tree i.e., fix the right  // child of predecessor  else {  pre->right = NULL;    cnt++;  if (cnt == k) return curr->data;    curr = curr->right;  }  }  }    // If k is greater than size of   // BST, return -1.  return -1; }  //Driver Code Starts struct Node* createNode(int x) {  struct Node* newNode =   (struct Node*)malloc(sizeof(struct Node));  newNode->data = x;  newNode->left = NULL;  newNode->right = NULL;  return newNode; } int main() {    // Binary search tree  // 20  // / \  // 8 22  // / \  // 4 12  // / \  // 10 14  struct Node* root = createNode(20);  root->left = createNode(8);  root->right = createNode(22);  root->left->left = createNode(4);  root->left->right = createNode(12);  root->left->right->left = createNode(10);  root->left->right->right = createNode(14);  int k = 3;  printf("%d ", kthSmallest(root, k));  return 0; } //Driver Code Ends

Java

//Driver Code Starts // Java program to find kth smallest value in BST 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 element in a BST.  static int kthSmallest(Node root, int k) {  int cnt = 0;  Node curr = root;    while (curr != null) {    // if left child is null, check   // curr node and move to right node.  if (curr.left == null) {  cnt++;    // If curr is kth smallest node   if (cnt == k) return curr.data;    curr = curr.right;  } else {    // Find the inorder predecessor of curr  Node pre = curr.left;  while (pre.right != null && pre.right != curr)  pre = pre.right;  // Make curr as the right child of its  // inorder predecessor and move to   // left node.  if (pre.right == null) {  pre.right = curr;  curr = curr.left;  } else {    // Revert the changes made in the 'if' part to  // restore the original tree i.e., fix the right  // child of predecessor  pre.right = null;    cnt++;  if (cnt == k) return curr.data;    curr = curr.right;  }  }  }    // If k is greater than size of   // BST, return -1.  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

Python

#Driver Code Starts # Python program to find kth smallest value in BST class Node: def __init__(self, x): self.data = x self.left = None self.right = None #Driver Code Ends   # Function to find kth smallest element in a BST. def kthSmallest(root, k): cnt = 0 curr = root while curr: # if left child is null, check  # curr node and move to right node. if not curr.left: cnt += 1 # If curr is kth smallest node  if cnt == k: return curr.data curr = curr.right else: # Find the inorder predecessor of curr pre = curr.left while pre.right and pre.right != curr: pre = pre.right # Make curr as the right child of its # inorder predecessor and move to  # left node. if not pre.right: pre.right = curr curr = curr.left else: # Revert the changes made in the 'if' part to # restore the original tree i.e., fix the right # child of predecessor pre.right = None cnt += 1 if cnt == k: return curr.data curr = curr.right # If k is greater than size of  # BST, return -1. 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 // C# program to find kth smallest value in BST using System; 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 element in a BST.  static int kthSmallest(Node root, int k) {  int cnt = 0;  Node curr = root;    while (curr != null) {    // if left child is null, check   // curr node and move to right node.  if (curr.left == null) {  cnt++;    // If curr is kth smallest node   if (cnt == k) return curr.data;    curr = curr.right;  } else {    // Find the inorder predecessor of curr  Node pre = curr.left;  while (pre.right != null && pre.right != curr)  pre = pre.right;  // Make curr as the right child of its  // inorder predecessor and move to   // left node.  if (pre.right == null) {  pre.right = curr;  curr = curr.left;  } else {    // Revert the changes made in the 'if' part to  // restore the original tree i.e., fix the right  // child of predecessor  pre.right = null;    cnt++;  if (cnt == k) return curr.data;    curr = curr.right;  }  }  }    // If k is greater than size of   // BST, return -1.  return -1;  }  //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

JavaScript

//Driver Code Starts // JavaScript program to find kth smallest value in BST class Node {  constructor(x) {  this.data = x;  this.left = null;  this.right = null;  } } //Driver Code Ends   // Function to find kth smallest element in a BST. function kthSmallest(root, k) {  let cnt = 0;  let curr = root;    while (curr !== null) {    // if left child is null, check   // curr node and move to right node.  if (curr.left === null) {  cnt++;    // If curr is kth smallest node   if (cnt === k) return curr.data;    curr = curr.right;  } else {    // Find the inorder predecessor of curr  let pre = curr.left;  while (pre.right !== null && pre.right !== curr)  pre = pre.right;  // Make curr as the right child of its  // inorder predecessor and move to left node.  if (pre.right === null) {  pre.right = curr;  curr = curr.left;  } else {    // Revert the changes made in the 'if' part to  // restore the original tree i.e., fix the right  // child of predecessor  pre.right = null;    cnt++;  if (cnt === k) return curr.data;    curr = curr.right;  }  }  }    // If k is greater than size of   // BST, return -1.  return -1; } // Driver Code  //Driver Code Starts // 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