Kth Smallest Element In a Bst
The briefingthe full drill, in my own words
The drill: Find the k-th smallest value stored in a BST — the tree's shape encodes sorted order for free, if you traverse it the right way.
A binary search tree and a rank k arrive together, and the task is naming which value sits at position k when every node's value is listed in ascending order.
BSTs already encode sorted order in their shape — the way you walk it decides whether you're rediscovering that order the hard way or reading it off for free.
k always falls inside the number of nodes present, so the only real question is finding the value that lands at that rank and returning it.
- k always falls within the tree's actual node count
- tree sizes reach into the tens of thousands
- values are unique across the tree, consistent with BST ordering
- k is 1-indexed — k=1 means the smallest value
The hintstake only what you need
HINT 1 THE NUDGE
A BST's inorder traversal visits values in ascending sorted order — that fact alone solves most of this problem.
HINT 2 THE STRUCTURE
You don't need every value, just the k-th one. What lets a traversal stop the instant it produces the k-th value, instead of finishing the whole tree?
HINT 3 ONE STEP FROM THE ANSWER
Iterative inorder with an explicit stack: push left spines, pop, count each pop — the k-th pop's value is the answer, and the stack lets you return immediately.
Coach's boardthe pattern, step by step
Push every left child down to the bottom — the stack's TOP is always the next-smallest unvisited value. Target k=4.
The splitstwo paces, two languages
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
node = root
count = 0
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
count += 1
if count == k:
return node.val
node = node.right
return -1class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
result: List[int] = []
def inorder(node: Optional[TreeNode]) -> None:
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result[k - 1]class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode node = root;
int count = 0;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
count++;
if (count == k) {
return node.val;
}
node = node.right;
}
return -1;
}
}class Solution {
public int kthSmallest(TreeNode root, int k) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result.get(k - 1);
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
inorder(node.left, result);
result.add(node.val);
inorder(node.right, result);
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED