230. Kth Smallest Element in a BST

Problem Link

Inorder traversal on a BST visits nodes in ascending order**. This property allows us to directly find the k-th smallest element, but think about how to do it without storing all values.

We perform an inorder traversal (left → node → right) while maintaining a counter k. Each time we visit a node, we decrement k. When k reaches zero, the current node’s value is exactly the k-th smallest element.

When implementing this recursively, you can use global variables for k and res which would capture result relatively easy. In below code, the helper function implements Inorder traversal and when we reach \(k=0\), we'll simply capture that node instead of worrying about returning the values back up to recursion. By leveraging the BST property and stopping as soon as the answer is found, we avoid unnecessary work and extra space.

Runtime Complexity

Time: \(O(h + k)\) in the best case, \(O(n)\) in the worst case

Space: \(O(h)\), where \(h\) is the height of the tree due to recursion stack

PythonGo

class Solution:
    def _helper(self, node):
        if not node:
            return

        self._helper(node.left)
        self.k-=1
        if self.k == 0:
            self.res = node.val
            return

        self._helper(node.right)
        return

    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.k = k
        self.res = -1
        self._helper(root)
        return self.res

func kthSmallest(root *TreeNode, k int) int {
    var res int
    var helper func(node *TreeNode)
    helper = func(node *TreeNode) {
        if node == nil {
            return
        }
        helper(node.Left)
        k--
        if k == 0 {
            res = node.Val
            return
        }
        helper(node.Right)
    }
    helper(root)
    return res
}

---