Kth Smallest Element in a BST

Problem

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Examples

The brute-force approach

Collect all values via inorder traversal into an array. Return array[k-1].

vals = []
def inorder(node):
    if not node: return
    inorder(node.left)
    vals.append(node.val)
    inorder(node.right)
inorder(root)
return vals[k-1]

O(n) time and space. Stores all values even though we only need the k-th.

Spotting the pattern

This is a Tree Traversal problem. The key question to ask yourself:

Why does inorder traversal (left → node → right) of a BST produce values in sorted order? What property of a BST makes this true?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.