230. Kth Smallest Element in a BST (Medium)

Problem

Given the root of a BST and an integer k, return the k-th smallest value in the tree (1-indexed).

Example

• root = [3,1,4,null,2], k = 1 → 1
• root = [5,3,6,2,4,null,null,1], k = 3 → 3

Follow-up: if the BST is frequently modified and you need many kth-smallest queries, how would you optimize?

LeetCode 230 · Link · Medium

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Full inorder traversal into a list

Collect all values in sorted order via inorder, then index.

Python

def kth_smallest(root, k):
    def inorder(node):                          # L1: recursive inorder
        return inorder(node.left) + [node.val] + inorder(node.right) if node else []
    return inorder(root)[k - 1]                 # L2: O(1) index

Swift

final class Solution { func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int { var values: [Int] = []; func traverse(_ node: TreeNode?) { guard let node else { return }; traverse(node.left); values.append(node.val); traverse(node.right) }; traverse(root); return values[k - 1] } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, k = target rank.

Line	Per-call cost	Times executed	Contribution
L1 (inorder + concat)	$O(n)$ per call due to list concat	n	$O(n²)$ ← dominates
L2 (index)	$O(1)$	1	$O(1)$

The + operator on lists creates a new list each time, making this $O(n²)$ as written. Using append + generator would make it $O(n)$.

Complexity

• Time: $O(n)$ with a proper append-based inorder; $O(n²)$ with list concatenation as written.
• Space: $O(n)$ for the list.

Works but doesn’t exploit “early termination” once we’ve hit k.

Approach 2: Recursive inorder with a counter (early exit)

Same inorder, but track a running count and short-circuit.

Python

def kth_smallest(root, k):
    count = [0]
    result = [None]
    def inorder(node):
        if not node or result[0] is not None:
            return                              # L1: base / already found
        inorder(node.left)                     # L2: recurse left
        count[0] += 1                          # L3: O(1) increment
        if count[0] == k:
            result[0] = node.val               # L4: O(1) record answer
            return
        inorder(node.right)                    # L5: recurse right
    inorder(root)
    return result[0]

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function kthSmallest(root: TreeNode | null, k: number): number {
    let count = 0;
    let result = -1;
    function inorder(node: TreeNode | null): void {
        if (!node || result !== -1) return;             // L1: base / already found
        inorder(node.left);                             // L2: recurse left
        count++;                                        // L3: O(1) increment
        if (count === k) { result = node.val; return; } // L4: O(1) record answer
        inorder(node.right);                            // L5: recurse right
    }
    inorder(root);
    return result;
}

Swift

final class Solution { func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int { var remaining = k, answer = 0; func visit(_ node: TreeNode?) { guard let node, remaining > 0 else { return }; visit(node.left); remaining -= 1; if remaining == 0 { answer = node.val; return }; visit(node.right) }; visit(root); return answer } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, k = target rank.

Line	Per-call cost	Times executed	Contribution
L2 (recurse left)	$O(1)$ dispatch	h + k visits	$O(h + k)$
L3 (increment)	$O(1)$	k	$O(k)$
L4/L5 (record + recurse right)	$O(1)$	h + k	$O(h + k)$ ← dominates

Once count == k, all subsequent calls return immediately via L1’s guard.

Complexity

• Time: $O(h + k)$. Early exit after k visits.
• Space: $O(h)$ recursion.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative inorder with an explicit stack (optimal)

Simulate inorder with a stack; pop exactly k times.

Python

def kth_smallest(root, k):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)      # L1: push left spine
            node = node.left
        node = stack.pop()          # L2: O(1) pop
        k -= 1                      # L3: O(1) decrement
        if k == 0:
            return node.val         # L4: O(1) return kth
        node = node.right           # L5: move to right subtree
    return -1

TypeScript

function kthSmallest(root: TreeNode | null, k: number): number {
    const stack: TreeNode[] = [];
    let node: TreeNode | null = root;
    while (node || stack.length) {
        while (node) {
            stack.push(node);       // L1: push left spine
            node = node.left;
        }
        node = stack.pop()!;        // L2: O(1) pop
        k--;                        // L3: O(1) decrement
        if (k === 0) return node.val; // L4: O(1) return kth
        node = node.right;          // L5: move to right subtree
    }
    return -1;
}

Swift

final class Solution { func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int { var stack: [TreeNode] = [], current = root, remaining = k; while current != nil || !stack.isEmpty { while let node = current { stack.append(node); current = node.left }; let node = stack.removeLast(); remaining -= 1; if remaining == 0 { return node.val }; current = node.right }; return 0 } }

Where the time goes, line by line

Variables: n = number of nodes in the tree, h = tree height, k = target rank.

Line	Per-call cost	Times executed	Contribution
L1 (push spine)	$O(1)$ per push	h + k total	$O(h + k)$
L2/L3 (pop + decrement)	$O(1)$	k	$O(k)$
L4/L5 (return or advance)	$O(1)$	h + k	$O(h + k)$ ← dominates (all lines tie)

We push nodes lazily (only down the left spine), so we never visit more than h + k nodes.

Complexity

• Time: $O(h + k)$, driven by L1/L2 processing h + k nodes.
• Space: $O(h)$.

Follow-up (mutable tree)

If the tree changes frequently, augment each node with left_subtree_count. Then kth-smallest becomes $O(h)$ without traversal, compare k against left.count + 1 at each node to decide which direction to go. That’s how many interview databases and self-balancing BST libraries implement $O(log n)$ order statistics.

Summary

Approach	Time	Space
Full inorder list	$O(n)$	$O(n)$
Recursive inorder + counter	$O(h + k)$	$O(h)$
Iterative inorder + stack	$O(h + k)$	$O(h)$

The iterative inorder is the canonical answer. It’s also the natural structure for related problems (next-in-inorder, inorder successor).

Test cases

Python

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

def build_tree(vals):
    if not vals: return None
    root = TreeNode(vals[0])
    q = [root]
    i = 1
    while q and i < len(vals):
        node = q.pop(0)
        if i < len(vals) and vals[i] is not None:
            node.left = TreeNode(vals[i])
            q.append(node.left)
        i += 1
        if i < len(vals) and vals[i] is not None:
            node.right = TreeNode(vals[i])
            q.append(node.right)
        i += 1
    return root

def kth_smallest(root, k):
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    return -1

def _run_tests():
    # [3,1,4,null,2], k=1 → 1
    assert kth_smallest(build_tree([3, 1, 4, None, 2]), 1) == 1
    # [5,3,6,2,4,null,null,1], k=3 → 3
    assert kth_smallest(build_tree([5, 3, 6, 2, 4, None, None, 1]), 3) == 3
    # single node, k=1
    assert kth_smallest(build_tree([1]), 1) == 1
    # k = n (largest)
    assert kth_smallest(build_tree([3, 1, 4, None, 2]), 4) == 4
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

class TreeNode {
    val: number; left: TreeNode | null; right: TreeNode | null;
    constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function buildTree(vals: (number | null)[]): TreeNode | null {
    if (!vals.length) return null;
    const root = new TreeNode(vals[0] as number);
    const q: TreeNode[] = [root];
    let i = 1;
    while (q.length && i < vals.length) {
        const node = q.shift()!;
        if (i < vals.length && vals[i] !== null) { node.left = new TreeNode(vals[i] as number); q.push(node.left); }
        i++;
        if (i < vals.length && vals[i] !== null) { node.right = new TreeNode(vals[i] as number); q.push(node.right); }
        i++;
    }
    return root;
}

function kthSmallest(root: TreeNode | null, k: number): number {
    const stack: TreeNode[] = [];
    let node: TreeNode | null = root;
    while (node || stack.length) {
        while (node) { stack.push(node); node = node.left; }
        node = stack.pop()!;
        k--;
        if (k === 0) return node.val;
        node = node.right;
    }
    return -1;
}

console.assert(kthSmallest(buildTree([3, 1, 4, null, 2]), 1) === 1);
console.assert(kthSmallest(buildTree([5, 3, 6, 2, 4, null, null, 1]), 3) === 3);
console.assert(kthSmallest(buildTree([1]), 1) === 1);
console.assert(kthSmallest(buildTree([3, 1, 4, null, 2]), 4) === 4);
console.log("all tests pass");

Related data structures

• Binary Trees & BSTs, inorder traversal yields sorted order
• Stacks, iterative inorder

Related concepts

• Tree Traversal, the recursive or iterative visit pattern for carrying path and subtree state.
• DFS, the depth first traversal habit of following one branch before returning.