230. Kth Smallest Element in a BST

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Recursive In-Order	Use DFS with in-order traversal to visit nodes in sorted order. Count visited nodes and return value when counter equals \(k\).	\(O(H + k)\)	\(O(H)\)
Iterative In-Order	Use stack to simulate in-order traversal iteratively. Process left subtree, visit node, then right subtree until kth element found.	\(O(H + k)\)	\(O(H)\)

Time Complexity Explanation: \(O(H + k)\) where \(H\) is tree height. We traverse at most \(H\) nodes to reach leftmost node, then visit \(k\) nodes in sorted order.

Space Complexity Explanation: \(O(H)\) where \(H\) is tree height. Recursive approach uses call stack of depth \(H\). Iterative approach uses explicit stack that can grow up to \(H\) nodes in worst case (skewed tree).

Implementation

PythonJavaScriptGo

Recursive

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        ans = float("inf")
        counter = 0
        def dfs(node: TreeNode, k: int) -> None:
            nonlocal ans, counter

            if node.left:
                dfs(node.left, k)

            counter += 1
            if counter == k:
                ans = node.val
                return

            if node.right:
                dfs(node.right, k)

        dfs(root, k)
        return ans

Iterative

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        counter = 0
        stack = []
        current_node = root

        while current_node or stack:
            while current_node:
                stack.append(current_node)
                current_node = current_node.left

            current_node = stack.pop()
            counter += 1
            if counter == k:
                return current_node.val
            current_node = current_node.right
        return