Kth Smallest Element in a BST solution and explanation
Google
Cisco
TCS
9 more videos on this problem
Kth Smallest Element in a BST - Leetcode 230 - PythonNeetCode · 10:56 · 266K views
Kth Smallest Element in a BST | Leetcode #230Techdose · 13:07 · 50K views
Kth Smallest Element in a BST - Leetcode 230 - Trees (Python)Greg Hogg · 7:46 · 14K views
Kth Smallest Element in BST | Leetcode - 230 | Trees - 16Algorithms Made Easy · 4:52 · 3K views
Kth Smallest Element in a BST - LeetCode 230 - Python (Recursive and Iterative!) #leetcodeDeepti Talesra · 15:43 · 3K views
Kth Smallest Element in a BST - LeetCode 230 - JavaScriptAlgoJS · 4:25 · 1K views
Kth Smallest Element in a BST | Leetcode 230| Matrix 2D 🔥🔥 | Live coding sessionCoding Decoded · 7:34 · 714 views
Kth Smallest In BST | LeetCode 230 (Medium)Destination FAANG · 7:35 · 709 views
Kth Smallest Element in a BST | LeetCode 230 | JavaThe TryIt Project · 10:30 · 425 views
Kth Smallest Element in a BST | Leetcode | Java | CODING INTERVIEW QUESTIONWeAreTechies · 6:55 · 289 views
The problem
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes 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 <= 1040 <= Node.val <= 104
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Approach overview
Problem Overview: Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all nodes. The key observation is that an in-order traversal of a BST visits nodes in strictly increasing order.
The BST property makes this problem straightforward once you recognize the traversal order. In-order traversal processes nodes as left → root → right, which naturally produces a sorted sequence. Instead of storing the entire sequence, you only need to count nodes until the kth element appears.
Approach 1: In-Order Traversal (Recursive) (O(n) time, O(h) space)
This approach performs a standard in-order traversal of the tree. Maintain a counter that increments every time you visit a node. Once the counter equals k, return that node’s value immediately. Because a BST guarantees sorted order during in-order traversal, the kth visited node is the kth smallest element.
The recursion stack holds at most h nodes where h is the tree height. In a balanced tree this is O(log n), but in the worst case (skewed tree) it becomes O(n). This solution is simple, easy to reason about, and commonly expected in interviews involving tree traversal or depth-first search.
Approach 2: Morris In-Order Traversal (Iterative) (O(n) time, O(1) space)
Morris Traversal performs in-order traversal without recursion or an explicit stack. It temporarily modifies the tree by creating threaded links from a node’s predecessor back to the current node. This allows traversal to return to parent nodes without storing them in memory.
During traversal, increment a counter each time a node is processed. When the counter reaches k, return the current value. After visiting a node, restore the modified pointers so the tree structure remains unchanged. This method achieves constant extra space while still visiting each node at most twice.
Morris traversal is especially useful when memory usage must stay minimal. It’s less commonly written in interviews but demonstrates strong understanding of binary search tree traversal mechanics.
Recommended for interviews: The recursive in-order traversal is the expected answer in most interviews because it directly uses the BST ordering property and is easy to implement quickly. Mentioning Morris traversal as a follow-up shows deeper knowledge of tree traversal optimizations and space reduction techniques.
Approach 1: In-Order Traversal (Recursive)
In a Binary Search Tree (BST), an in-order traversal visits nodes in ascending order. To find the kth smallest element, perform an in-order traversal and count the nodes until you reach the kth one.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
def inorder(node):
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
return inorder(root)[k - 1]class Solution {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public int kthSmallest(TreeNode root, int k) {
int[] result = new int[2];
inorder(root, result, k);
return result[1];
}
private void inorder(TreeNode node, int[] result, int k) {
if (node == null) return;
inorder(node.left, result, k);
if (++result[0] == k) {
result[1] = node.val;
return;
}
inorder(node.right, result, k);
}
}#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* node, int& k, int& result) {
if (!node || k <= 0) return;
inorder(node->left, k, result);
if (--k == 0) {
result = node->val;
return;
}
inorder(node->right, k, result);
}
int kthSmallest(TreeNode* root, int k) {
int result = -1;
inorder(root, k, result);
return result;
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var kthSmallest = function(root, k) {
let count = 0;
let result = null;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (++count === k) {
result = node.val;
return;
}
inorder(node.right);
}
inorder(root);
return result;
};#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode* root, int* k, int* found)
{
if (!root) return;
inorder(root->left, k, found);
if (--(*k) == 0) {
*found = root->val;
return;
}
inorder(root->right, k, found);
}
int kthSmallest(struct TreeNode* root, int k)
{
int found = 0;
inorder(root, &k, &found);
return found;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int KthSmallest(TreeNode root, int k) {
int result = 0;
InOrder(root, ref k, ref result);
return result;
}
private void InOrder(TreeNode node, ref int k, ref int result) {
if (node == null) return;
InOrder(node.left, ref k, ref result);
if (--k == 0) {
result = node.val;
return;
}
InOrder(node.right, ref k, ref result);
}
}This Python solution employs recursion to perform an in-order traversal, collecting node values in a list. The kth element is directly accessed by list indexing. This approach, however, uses O(n) space for storing the list.
Time Complexity: O(n), Space Complexity: O(n) (due to list storing all nodes).
Approach 2: Morris In-Order Traversal (Iterative)
Morris Traversal is a way to perform in-order traversal with O(1) extra space. This method modifies the tree's structure temporarily to avoid the recursive call stack. This approach uses the concept of threading where leaf nodes point to their in-order successor to facilitate traversal.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
current = root
count = 0
result = 0
while current:
if not current.left:
count += 1
if count == k:
return current.val
current = current.right
else:
predecessor = current.left
while predecessor.right and predecessor.right is not current:
predecessor = predecessor.right
if not predecessor.right:
predecessor.right = current
current = current.left
else:
predecessor.right = None
count += 1
if count == k:
return current.val
current = current.rightclass Solution {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public int kthSmallest(TreeNode root, int k) {
TreeNode curr = root;
int count = 0;
int result = 0;
while (curr != null) {
if (curr.left == null) {
if (++count == k) result = curr.val;
curr = curr.right;
} else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) pre = pre.right;
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
} else {
pre.right = null;
if (++count == k) result = curr.val;
curr = curr.right;
}
}
}
return result;
}
}#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int kthSmallest(TreeNode* root, int k) {
TreeNode* curr = root;
TreeNode* pre = nullptr;
int count = 0;
int result = 0;
while (curr) {
if (!curr->left) {
if (++count == k) result = curr->val;
curr = curr->right;
} else {
pre = curr->left;
while (pre->right && pre->right != curr) pre = pre->right;
if (!pre->right) {
pre->right = curr;
curr = curr->left;
} else {
pre->right = nullptr;
if (++count == k) result = curr->val;
curr = curr->right;
}
}
}
return result;
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var kthSmallest = function(root, k) {
let count = 0;
let current = root;
let result = null;
while (current) {
if (!current.left) {
count++;
if (count === k) return current.val;
current = current.right;
} else {
let predecessor = current.left;
while (predecessor.right && predecessor.right !== current) {
predecessor = predecessor.right;
}
if (!predecessor.right) {
predecessor.right = current;
current = current.left;
} else {
predecessor.right = null;
count++;
if (count === k) return current.val;
current = current.right;
}
}
}
};#include <stdio.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int kthSmallest(struct TreeNode* root, int k) {
struct TreeNode* curr = root;
struct TreeNode* pre;
int count = 0;
int result;
while (curr != NULL) {
if (curr->left == NULL) {
if (++count == k) result = curr->val;
curr = curr->right;
} else {
pre = curr->left;
while (pre->right != NULL && pre->right != curr) pre = pre->right;
if (pre->right == NULL) {
pre->right = curr;
curr = curr->left;
} else {
pre->right = NULL;
if (++count == k) result = curr->val;
curr = curr->right;
}
}
}
return result;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public int KthSmallest(TreeNode root, int k) {
TreeNode curr = root;
int count = 0;
while (curr != null) {
if (curr.left == null) {
count++;
if (count == k) return curr.val;
curr = curr.right;
} else {
TreeNode pre = curr.left;
while (pre.right != null && pre.right != curr) pre = pre.right;
if (pre.right == null) {
pre.right = curr;
curr = curr.left;
} else {
pre.right = null;
count++;
if (count == k) return curr.val;
curr = curr.right;
}
}
}
return -1; // This line is never reached if the tree contains the kth smallest element.
}
}The Python code implements Morris In-Order Traversal, leading to O(1) auxiliary space usage. The traversal efficiently visits nodes while keeping changes to the tree structure temporary.
Time Complexity: O(n), Space Complexity: O(1).
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function kthSmallest(root: TreeNode | null, k: number): number {
const dfs = (root: TreeNode | null) => {
if (root == null) {
return -1;
}
const { val, left, right } = root;
const l = dfs(left);
if (l !== -1) {
return l;
}
k--;
if (k === 0) {
return val;
}
return dfs(right);
};
return dfs(root);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
stk := []*TreeNode{}
for root != nil || len(stk) > 0 {
if root != nil {
stk = append(stk, root)
root = root.Left
} else {
root = stk[len(stk)-1]
stk = stk[:len(stk)-1]
k--
if k == 0 {
return root.Val
}
root = root.Right
}
}
return 0
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: Option<Rc<RefCell<TreeNode>>>, res: &mut Vec<i32>, k: usize) {
if let Some(node) = root {
let mut node = node.borrow_mut();
Self::dfs(node.left.take(), res, k);
res.push(node.val);
if res.len() >= k {
return;
}
Self::dfs(node.right.take(), res, k);
}
}
pub fn kth_smallest(root: Option<Rc<RefCell<TreeNode>>>, k: i32) -> i32 {
let k = k as usize;
let mut res: Vec<i32> = Vec::with_capacity(k);
Self::dfs(root, &mut res, k);
res[k - 1]
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-Order Traversal (Recursive) | Time Complexity: O(n), Space Complexity: O(n) (due to list storing all nodes). |
| Morris In-Order Traversal (Iterative) | Time Complexity: O(n), Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal (Recursive) | O(n) | O(h) | General interview solution; simple and leverages BST ordering |
| Morris In-Order Traversal | O(n) | O(1) | When minimizing extra memory or demonstrating advanced traversal techniques |
Frequently asked questions
Is Kth Smallest Element in a BST easy or hard?
The problem is rated Medium because recognizing the in-order traversal property of BSTs is the key insight. Once that observation is made, the implementation is straightforward, but interviewers may ask follow-ups such as reducing space to O(1) using Morris traversal.
Kth Smallest Element in a BST Python/Java solution
Python and Java implementations typically use recursive in-order traversal with a global or reference counter. Each node visit increments the counter until the kth node is found. The same logic works in C++, JavaScript, and other languages because it depends only on tree traversal order.
How to solve Kth Smallest Element in a BST in O(n)?
Perform an in-order traversal of the BST and maintain a counter for visited nodes. Increment the counter each time a node is processed. When the counter equals k, return that node’s value. This guarantees O(n) time because each node is visited at most once.
What is the best approach for Kth Smallest Element in a BST?
In-order traversal is the best approach because a Binary Search Tree outputs nodes in sorted order when traversed left → root → right. Counting nodes during traversal allows you to stop once the kth node is reached. This method runs in O(n) time and O(h) space where h is the tree height.
Is Kth Smallest Element in a BST asked at Google/Amazon/Meta?
Kth Smallest Element in a BST appears frequently in interviews at companies like Amazon, Google, and Meta. It tests understanding of BST ordering, depth-first traversal, and the ability to optimize space using techniques such as Morris traversal.
What data structure is used in Kth Smallest Element in a BST?
The core data structure is a Binary Search Tree. Solutions rely on depth-first traversal, usually in-order traversal, and may use recursion stacks or pointer threading (Morris traversal) to navigate the tree efficiently.
What is the time complexity of Kth Smallest Element in a BST?
Most solutions run in O(n) time because in the worst case you may need to visit every node. Recursive in-order traversal uses O(h) space for the recursion stack, while Morris traversal reduces extra space to O(1) by temporarily modifying tree pointers.