Approach Summary
In-order traversal of BST visits nodes in ascending order. Count k nodes; return on the kth.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: In-Order Traversal with Early Exit (Optimal) | O(H + k) | O(H) | Traverse left-root-right, stopping traversal as soon as the kth visited element is reached. |
| 2 Approach 2: Recursive In-Order Traversal to List (Baseline) | O(n) | O(n) | Collects all node values in ascending order via full in-order traversal, returning list[k - 1]. |
Step 1: Baseline
Approach 1: In-Order Traversal with Early Exit (Optimal)
Time: O(H + k)
Space: O(H)
In-order traversal of a BST enumerates elements in ascending order. Increment counter upon visiting each node; as soon as counter == k, record answer and terminate.
Approach 1: In-Order Traversal with Early Exit (Optimal) Implementation
Approach 1: In-Order Traversal with Early Exit (Optimal)
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
if (--k == 0) return curr.val;
curr = curr.right;
}
return -1;
}
}class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*> s;
TreeNode* curr = root;
while (curr != NULL || !s.empty()) {
while (curr != NULL) {
s.push(curr);
curr = curr->left;
}
curr = s.top(); s.pop();
if (--k == 0) return curr->val;
curr = curr->right;
}
return -1;
}
};class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
k -= 1
if k == 0:
return curr.val
curr = curr.rightfunction kthSmallest(root, k) {
const stack = [];
let curr = root;
while (curr || stack.length) {
while (curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
k--;
if (k === 0) return curr.val;
curr = curr.right;
}
} Step 2: Most Optimized
Approach 2: Recursive In-Order Traversal to List (Baseline)
Time: O(n)
Space: O(n)
Performs complete in-order traversal (left, root, right) of the BST and appends every element to a list. Because BST in-order is sorted, returns the (k-1)-th index.
Approach 2: Recursive In-Order Traversal to List (Baseline) Implementation
Approach 2: Recursive In-Order Traversal to List (Baseline)
class Solution {
private List<Integer> vals = new ArrayList<>();
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
vals.add(node.val);
inorder(node.right);
}
public int kthSmallest(TreeNode root, int k) {
inorder(root);
return vals.get(k - 1);
}
}class Solution {
vector<int> vals;
void inorder(TreeNode* node) {
if (!node) return;
inorder(node->left);
vals.push_back(node->val);
inorder(node->right);
}
public:
int kthSmallest(TreeNode* root, int k) {
inorder(root);
return vals[k - 1];
}
};class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
vals = []
def inorder(node):
if not node: return
inorder(node.left)
vals.append(node.val)
inorder(node.right)
inorder(root)
return vals[k - 1]function kthSmallest(root, k) {
const vals = [];
function inorder(node) {
if (!node) return;
inorder(node.left);
vals.push(node.val);
inorder(node.right);
}
inorder(root);
return vals[k - 1];
}Edge Cases to Watch
- k = 1 (smallest element; leftmost node in tree)
- k equals total number of nodes (largest element; rightmost node)
- Left-skewed tree
Algorithmic Pattern
View Pattern Guide →
Master the Trees / DFS Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Trees / DFS pattern.
Framework: Trees / DFS • Interview Prep: Tested at FAANG •
Explore all Trees / DFS problems & invariants →
How to Recognize This Pattern
- "kth element in BST"
- In-order traversal of BST = sorted ascending
Complexity Analysis
Time Complexity
O(H + k)
Space Complexity
O(H)
Tags
Tree DFS BST Binary Tree
Frequently Asked Questions
What is the optimal time and space complexity for Kth Smallest Element in a BST?
The optimal solution for Kth Smallest Element in a BST achieves O(H + k) runtime complexity and requires O(H) auxiliary space. Time complexity is O(H + k) where H is tree height, because we only visit the first k nodes in sorted order. Space complexity is O(H) for the call stack.
How do I identify that Kth Smallest Element in a BST requires the Trees / DFS pattern?
In technical interviews, look for key problem signals: "kth element in BST"; In-order traversal of BST = sorted ascending. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Trees / DFS strategy.
What critical edge cases must be handled in Kth Smallest Element in a BST?
Essential edge cases to verify include: k = 1 (smallest element; leftmost node in tree); k equals total number of nodes (largest element; rightmost node); Left-skewed tree. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Kth Smallest Element in a BST?
Kth Smallest Element in a BST is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, Microsoft.