GeeksforGeeks Medium

Kth Smallest and Largest in BST

Find both the k-th smallest and k-th largest BST values.

bstinorder

02

Intuition

k-th smallest is the k-th node of inorder (left-node-right); k-th largest is the k-th node of REVERSE inorder (right-node-left). Two early-stopping traversals — or one, since k-th largest = (n−k+1)-th smallest.

How to spot this pattern

In-order gives ascending values; reverse in-order — right, node, left — gives descending. So the k-th largest is the k-th smallest of the mirrored traversal, and one parameterised function answers both. Recognising that a traversal's direction is just a swap of two recursive calls saves writing the second algorithm.

03

Approach

1

Forward inorder for smallest

Count nodes as visited; stop at k.

2

Reverse inorder for largest

Mirror the traversal (right first) — descending stream, stop at k.

3

Or count once

Knowing n converts largest into a second smallest query; useful when n is cached.

04

Solution & live demo

▶1def kth_smallest_largest(root, k):
▶2    def inorder(node, reverse, count, out):
▶3        if not node or out: return
▶4        a, b = (node.right, node.left) if reverse else (node.left, node.right)
▶5        inorder(a, reverse, count, out)
▶6        if not out:
▶7            count[0] += 1
▶8            if count[0] == k: out.append(node.val); return
▶9            inorder(b, reverse, count, out)
▶10    small, large = [], []
▶11    inorder(root, False, [0], small)
▶12    inorder(root, True, [0], large)
▶13    return small[0], large[0]

05

Common pitfalls

Sorting all values to pick both

✗ Wrong

vals = sorted(inorder(root))
return vals[k-1], vals[-k]

✓ Right

inorder(root, False, [0], small)
inorder(root, True,  [0], large)

A BST is already ordered — re-sorting throws that away and costs O(n log n) plus O(n) space. Each traversal can stop as soon as it has counted k nodes.

Not stopping once the answer is found

✗ Wrong

def inorder(node, ...):
    inorder(node.left, ...)
    count[0] += 1
    if count[0] == k: out.append(node.val)
    inorder(node.right, ...)

✓ Right

if not node or out: return
...
if count[0] == k: out.append(node.val); return

Without the early exit the traversal continues past the target and the counter keeps advancing, so a later node can be appended too. Checking out at the top prunes every remaining branch.

Passing the counter as a plain integer

✗ Wrong

def inorder(node, count):
    count += 1

✓ Right

def inorder(node, reverse, count, out):
    count[0] += 1

Integers are immutable in Python, so count += 1 rebinds a local and the increment is lost when the frame returns. The count must be shared across the whole traversal — a one-element list (or a class attribute) provides that.

06

Edge cases

k = 1

Smallest = leftmost node, largest = rightmost.

k > n

Traversal exhausts → report not found.

07

Complexity

Time

O(h + k)

Space

O(h)

Two early-exit traversals.