Given the root of a binary search tree and an integer k, return the kth smallest value among all the node values in the tree.
Example
Input root = [3,1,4,null,2], k = 1
Output 1
Key Pointers
An in-order traversal of a BST visits nodes in strictly increasing order — that turns "kth smallest" into "kth value visited."
Stop as soon as the kth value is reached instead of building the full sorted list, to avoid unnecessary work.
An iterative in-order traversal with an explicit stack makes early-stopping straightforward.
Step-by-Step Analysis
Initialize an empty stack and set node = root.
Push every left descendant onto the stack until reaching None.
Pop a node, decrement k; if k reaches 0, return that node's value.
Otherwise move to node.right and repeat the left-pushing step.
Complexity
Time: O(h + k) — Space: O(h)
Code
def kthSmallest(root: TreeNode | None, k: int) -> int:
stack = []
node = root
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.val
node = node.right
Code Explanation
How the solution above works, piece by piece.
Inorder traversal of a BST yields values in ascending order, so the k-th visited node is the answer.
The inner loop pushes nodes while walking left, reaching the smallest unvisited value.
node = stack.pop() visits the next value in sorted order; decrement k.
When k hits 0, return it; otherwise continue into the right subtree.
O(h + k) time: it stops early instead of traversing the whole tree. O(h) stack.
Visual Walkthrough
Running it on root = [3, 1, 4, null, 2], k = 1:
An inorder walk (left, node, right) visits a BST in sorted order, shown by the badges. The iterative version stops as soon as it has popped k nodes; for k = 1 that's the leftmost node, 1.