Kth Smallest Element in a BST

mediumTests passed 2026-11-11v1.0.0
TC: O(H + k)|SC: O(H)
TreesOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Iterative inorder traversal using an explicit stack stops immediately on the `k`-th pop—visiting only `O(H + k)` nodes instead of traversing the entire tree.

2. Complexity Bounds & Proof

BST inorder yields elements in sorted ascending order; descending down the left spine pushes O(H) nodes and the first k pops return the k-th smallest.

3. Minimal Idiomatic Code

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack, curr = [], root
    while stack or curr:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        k -= 1
        if k == 0:
            return curr.val
        curr = curr.right
    return -1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Collecting all N elements into an array ignores early exit and uses unnecessary O(N) memory.
Follow-ups:- Frequent inserts/deletes + k-th queries: augment each BST node with `leftSubtreeSize` for O(H) order-statistic queries.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Validate Binary Search Tree (O(N))Lowest Common Ancestor of a Binary Search Tree (O(H))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.