Given the root of a binary search tree and a number k, return the k-th smallest value. k starts counting at 1.
DSA Animator › DSA Revision › Tree › Kth Smallest Element in a BST
Remember: inorder of a search tree is sorted. Stop early as soon as you have counted k nodes. The video solves Kth Smallest Element in a BST (LeetCode 230, Medium) with the Inorder Counting pattern from the Tree topic, and you can replay every step in the interactive Kth Smallest Element in a BST animation.
Given the root of a binary search tree and a number k, return the k-th smallest value. k starts counting at 1.
For the tree 5, with children 3 and 6, where 3 has children 2 and 4, and 2 has a left child 1, and k equal to 3, the answer is 3. The sorted values are 1, 2, 3, 4, 5, 6, and the third one is 3.
You could copy every value into an array, sort it, and pick index k minus 1. But a search tree already gives sorted order through an inorder traversal. And we can stop as soon as we reach the k-th value.
Inorder visits left, then the node, then right. In a search tree, that means values come out from smallest to largest. Count each node as it is visited. When the count reaches k, that node is the answer, and you can stop.
Go left from 5 to 3, then to 2, then to 1. 1 has no left child, so it is visited first, and the count is 1. Back at 2, the count becomes 2. Back at 3, the count becomes 3, which equals k. So the answer is 3, and the rest of the tree is never touched.
In code, use the iterative inorder loop with a stack. Go left as far as possible, pushing nodes. Pop a node, and decrease k. If k reaches 0, return that value, otherwise move to the right child. It's O of the height plus k time.
Remember: inorder of a search tree is sorted. Stop early as soon as you have counted k nodes.