Kth Smallest Element in a BST

Q: What if the tree changes often and I need this query many times?

Store in each node the size of its left subtree and keep it updated on insert and delete. Then compare k with that size at each node and go left, stop, or go right with k reduced. Each query becomes O(h).

Q: Can I use a heap instead?

You could push every value into a heap and pop k times, but that ignores the ordering the BST already gives you and costs O(n log n) or O(n + k log n). The in-order walk is simpler and faster here.

Q: Why do infrastructure roles meet this?

Ordered structures back many real lookups, such as sorted indexes in a database or an ordered map of timestamps. "Give me the k-th smallest" is how you read a percentile or the k-th oldest entry from them, and stopping early is what keeps it cheap.

mediumTrees

Given the root of a binary search tree and an integer k, return the k-th smallest value in the tree, counting from 1. You can assume 1 <= k <= n, where n is the number of nodes.

In a BST every left subtree holds smaller values and every right subtree larger ones. Trees are written in level order, with null for a missing child.

Examples

Example 1

Input: root = [5, 3, 7, 2, 4, null, 8], k = 3

Output: 4

Explanation: In ascending order the values are 2, 3, 4, 5, 7, 8.

Example 2

Input: root = [9, 4, null, 1], k = 1

Output: 1

Hints

Approach

Run the in-order traversal iteratively and stop at the k-th node.

Start at the root with an empty stack.
Go as far left as possible, pushing each node.
Pop a node. This is the next smallest value; decrease k. If k is now 0, return its value.
Move to the popped node's right child and repeat from step 2.

The stack holds at most one root-to-leaf path, and the walk touches only the nodes before the answer plus the path down to the smallest one, so it can stop long before visiting the whole tree.

ComplexityTime O(h + k)Space O(h)

Python

from typing import Optional
 
# 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: Optional["TreeNode"], k: int) -> int:
        stack = []
        cur = root
        while True:
            while cur:  # walk to the smallest unvisited node
                stack.append(cur)
                cur = cur.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            cur = node.right

Follow-up questions

Find the k-th largest value instead, using a reverse in-order traversal.
Support inserts and deletes while keeping each query at O(h).

Frequently asked questions

Store in each node the size of its left subtree and keep it updated on insert and delete. Then compare k with that size at each node and go left, stop, or go right with k reduced. Each query becomes O(h).

You could push every value into a heap and pop k times, but that ignores the ordering the BST already gives you and costs O(n log n) or O(n + k log n). The in-order walk is simpler and faster here.

Ordered structures back many real lookups, such as sorted indexes in a database or an ordered map of timestamps. "Give me the k-th smallest" is how you read a percentile or the k-th oldest entry from them, and stopping early is what keeps it cheap.

Problem statement