Kth Smallest Element In a Bst

A BST’s inorder traversal visits values in strictly increasing order, so the kth smallest value is simply the kth value produced by an inorder walk. The only question is whether to materialize the whole traversal first or to stop as soon as the kth value is reached.

Full Inorder Traversal

Time O(n)Space O(n)

Collect every value via inorder traversal into a list, then index directly into it.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def kthSmallest(self, root: TreeNode | None, k: int) -> int:
        values = []

        def inorder(node: TreeNode | None) -> None:
            if node is None:
                return
            inorder(node.left)
            values.append(node.val)
            inorder(node.right)

        inorder(root)
        return values[k - 1]

Complexity: every node is visited once → O(n) time, even when k is small. Storing every value → O(n) space.

Iterative Inorder with Early Stop

OptimalTime O(h + k)Space O(h)

Simulate the inorder traversal with an explicit stack, but instead of building a full list, decrement a counter each time a node is popped and return as soon as it hits zero — no need to visit the rest of the tree.

class Solution:
    def kthSmallest(self, 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

Tracing root = [5,3,6,2,4,null,null,1], k = 3:

1 / 3

comparingseenresult

Push left spine (5, 3, 2, 1). Pop 1 first: k becomes 2, not 0 yet.

Complexity: in the worst case only the left spine plus k pops are touched before stopping → O(h + k) time, versus a full O(n) scan when the answer lies early in the traversal. Space is the stack, bounded by tree height → O(h).

For the follow-up (frequent inserts/deletes plus repeated kth-smallest queries): augment each BST node with a size field (count of nodes in its subtree). Descend from the root comparing k against 1 + size(left) to decide whether to recurse left, return the current node, or recurse right with an adjusted k — an O(h) query. Keeping size correct under insert/delete costs O(h) extra bookkeeping per update, which is worthwhile if kth-smallest queries vastly outnumber modifications.