Binary Search TreesProblem 13 of 22
Find Kth smallest element in a BST
Problem Statement
Given a BST and a positive integer k, find the kth smallest element in the BST.
Example:
5
/ \
3 6
/ \
2 4
/
1
k = 3
Output: 3 (Elements in order: 1, 2, 3, 4, 5, 6)
k = 1
Output: 1 (Smallest element)
Approach 1: Brute Force (Inorder Traversal to Array)
Intuition
Inorder traversal of BST gives elements in sorted (ascending) order. The kth smallest is simply the kth element in this traversal.
Algorithm
- Perform inorder traversal to get sorted array
- Return array[k-1] (0-indexed)
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private void inorder(TreeNode root, List<Integer> nodes) {
if (root == null) return;
inorder(root.left, nodes);
nodes.add(root.val);
inorder(root.right, nodes);
}
public int kthSmallestBruteForce(TreeNode root, int k) {
List<Integer> nodes = new ArrayList<>();
inorder(root, nodes);
if (k > nodes.size() || k <= 0) {
return -1; // Invalid k
}
return nodes.get(k - 1);
}
}Complexity Analysis
- Time Complexity: O(n) - Complete traversal
- Space Complexity: O(n) - Storing all nodes
Approach 2: Optimal (Inorder with Early Termination)
Intuition
We don't need to traverse the entire tree. Stop as soon as we reach the kth element during inorder traversal.
Algorithm
- Perform inorder traversal
- Count nodes visited
- When count equals k, record the result and stop
- Use early termination to avoid unnecessary traversal
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int count = 0;
private int result = -1;
private void inorder(TreeNode root, int k) {
if (root == null || count >= k) return;
// Traverse left subtree
inorder(root.left, k);
// Process current node
count++;
if (count == k) {
result = root.val;
return;
}
// Traverse right subtree
inorder(root.right, k);
}
public int kthSmallest(TreeNode root, int k) {
count = 0;
result = -1;
inorder(root, k);
return result;
}
}Complexity Analysis
- Time Complexity: O(h + k) - Traverse to leftmost (h) then k nodes
- Space Complexity: O(h) - Recursion stack
Approach 3: Iterative (Stack-based)
Intuition
Use explicit stack for iterative inorder traversal. More control over traversal and avoids recursion overhead.
Algorithm
- Use stack to simulate inorder traversal
- Push left nodes until null
- Pop, process, then go right
- Stop at kth node
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int kthSmallestIterative(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
int count = 0;
while (curr != null || !stack.isEmpty()) {
// Go to leftmost
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
count++;
if (count == k) {
return curr.val;
}
curr = curr.right;
}
return -1; // k is larger than tree size
}
}Complexity Analysis
- Time Complexity: O(h + k)
- Space Complexity: O(h) - Stack space
Approach 4: Morris Traversal (O(1) Space)
Intuition
Morris traversal achieves inorder without recursion or stack by temporarily modifying tree structure using threaded pointers.
Algorithm
- If no left child, process current, go right
- If left child exists, find inorder predecessor
- If predecessor's right is null, make it point to current (create thread)
- If predecessor's right points to current, remove thread, process current
java
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int kthSmallestMorris(TreeNode root, int k) {
TreeNode curr = root;
int count = 0;
while (curr != null) {
if (curr.left == null) {
// No left child, process current
count++;
if (count == k) return curr.val;
curr = curr.right;
} else {
// Find inorder predecessor
TreeNode pred = curr.left;
while (pred.right != null && pred.right != curr) {
pred = pred.right;
}
if (pred.right == null) {
// Create thread
pred.right = curr;
curr = curr.left;
} else {
// Thread exists, remove it and process
pred.right = null;
count++;
if (count == k) return curr.val;
curr = curr.right;
}
}
}
return -1;
}
}Complexity Analysis
- Time Complexity: O(n) - Each edge traversed at most twice
- Space Complexity: O(1) - No extra space
Key Takeaways
- Inorder is sorted: BST inorder gives ascending order
- Early termination: Stop once kth element is found
- Stack vs Recursion: Both O(h) space, stack avoids overflow
- Morris Traversal: O(1) space but modifies tree temporarily
- This is LeetCode #230 - Kth Smallest Element in a BST
- For multiple queries, consider augmenting BST with subtree sizes
- Relation: kth smallest = (n-k+1)th largest