Return the k-th smallest value in a binary search tree, counting from 1.
3 / \ 1 4 k = 1 → 1 \ 2 2
To put this in plain English: you are given a binary search tree. If you were to list out all the numbers in the tree from smallest to largest, which number would be exactly at the k-th position? (1-indexed, so k=1 is the smallest).
The simplest way is to collect all the values into an array, sort the array, and grab the k-1 index.
How it works: You run any traversal (preorder, postorder, etc.), append every node's value to a list, call .sort() on the list, and return list[k-1].
Why it's too slow: Sorting takes O(n \log n) time, and storing all elements takes O(n) space. Even if you use an in-order traversal to skip the sorting step (since in-order on a BST yields sorted values automatically), building the full array still takes O(n) time and O(n) space. We don't want to process all n nodes if k is small. We want to stop exactly when we hit the k-th node.
An in-order traversal of a binary search tree visits the values in increasing order.
Left subtree, then the node, then the right subtree. Because everything on the left is smaller and everything on the right is larger, that order is sorted by construction.
So the k-th smallest is simply the k-th node visited in order. Walk in order, count, and stop at k.
The stopping matters. Collecting every value into a list and indexing works and is O(n) time and space; stopping early makes it O(h + k), which is much better when k is small.
class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [] # (1) node = root while stack or node: # (2) while node: # (3) go as far left as possible stack.append(node) node = node.left node = stack.pop() # (4) this is the next value in order k -= 1 # (5) if k == 0: return node.val node = node.right # (6) then explore its right subtree
ts
function kthSmallest(root: TreeNode | null, k: number): number { const stack: TreeNode[] = []; // (1) let node = root; while (stack.length || node) { // (2) while (node) { // (3) stack.push(node); node = node.left; } node = stack.pop()!; // (4) if (--k === 0) return node.val; // (5) node = node.right; // (6) } return -1;}
(1) A stack of nodes we still owe a visit to, and a pointer node that starts at the root. In a search tree, the smallest value is the leftmost node, so we will head left first.
(2) Keep going while there is a node to explore, or one waiting on the stack.
(3) Dive left as far as possible, pushing every node we pass. Each pushed node is smaller than its ancestors but bigger than everything in its own left subtree, so it must wait until that left subtree has been visited.
(4) Pop the next node in sorted order. When the dive hits a missing left child, the node on top of the stack has nothing smaller left unvisited. So it is the next value in increasing order.
(5) Count it.k -= 1 uses up one of the k values we need. When k reaches 0, this node is the k-th smallest, so return it. TypeScript writes this as --k === 0, which subtracts 1 first and then compares.
(6) Move to its right subtree. Everything there is bigger than this node but smaller than the ancestors still on the stack, so it comes next in order.
The iterative in-order walk is worth learning as a shape, because it is the only traversal where the iterative version is genuinely useful — it lets you stop mid-walk, which recursion cannot do cleanly.
Read it as three steps repeating:
Dive left, pushing every node you pass. The stack now holds the chain of ancestors you will come back to.
Pop. That node is next in sorted order, because everything smaller than it has already been visited.
Turn right and repeat, which handles its right subtree before returning to the ancestors on the stack.
The stack is doing exactly what the call stack would do in the recursive version — holding the nodes you still owe a visit to.
def kthSmallest(self, root, k): self.k = k self.answer = None def inorder(node): if not node or self.answer is not None: return inorder(node.left) self.k -= 1 if self.k == 0: self.answer = node.val return inorder(node.right) inorder(root) return self.answer
Shorter, but the early exit needs a guard at the top of every call, because a return only leaves one frame. That awkwardness is exactly why the iterative version is preferred here.
Time Complexity:O(h + k). To find the first (smallest) element, we must traverse down to the leftmost leaf, which takes O(h) steps where h is the tree's height. Then we pop and process k nodes. So total time is proportional to h + k. If the tree is balanced, h \approx \log n. If k is small, this is highly efficient. If k \approx n, it degrades to O(n).
Space Complexity:O(h). The maximum size of the stack at any given time is the length of a single path from the root down to a leaf, which is the height of the tree h. No additional space is needed.
"What if the tree is modified often and you need this frequently?"
Walking the tree for every query is O(h + k) each time, which is wasteful when queries are common. The answer is to augment the tree: store in each node the size of its subtree.
Then finding the k-th smallest becomes a single root-to-leaf walk:
let L = size of the left subtreeif k <= L → the answer is in the left subtreeif k == L + 1 → this node is the answerotherwise → go right, looking for the (k − L − 1)-th
That is O(h) per query, with no dependence on k at all. The cost is maintaining the sizes on insertion and deletion, which is O(h) per update, since only the nodes along one path change.
This is a genuinely important idea: storing an aggregate in each node so that queries become walks. It is how order-statistic trees work, and it is the same technique behind segment trees and Fenwick trees in 4.13.4.
Kth Largest Element in a BST — reverse in-order: right, node, left.
Range Sum of BST — prune whole subtrees that fall outside the range, using the ordering.
BST Iterator (LeetCode 173) — this exact stack, exposed as next() and hasNext(). It is O(1) amortized per call and O(h) space, which is the same argument as the monotonic stack in 4.8: each node is pushed once and popped once.