Kth smallest / Kth largest element in a BST

Medium

Problem

Return the kth smallest (or kth largest) value in a BST, with k counted from 1.

Example 1

Input:  root = [5, 3, 6, 2, 4, null, null, 1], k = 3
Output: kth smallest = 3

Also asked as: Find Kth smallest element in a BST · Find Kth largest element in a BST

Test cases

Case 1

Input:    [3,1,4,null,2], 1
Expected: 1

Case 2

Input:    [5,3,6,2,4,null,null,1], 3
Expected: 3

Case 3

Input:    [2,1,3], 3
Expected: 3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Controlled in-order (reverse in-order for largest)

Time O(h + k)Space O(h)

In-order visits values ascending; stop at the kth. For kth largest, do a reverse in-order (right, node, left).

function kthSmallest(root, k) {
const st = [];
let cur = root;
while (cur || st.length) {
while (cur) { st.push(cur); cur = cur.left; }
cur = st.pop();
if (--k === 0) return cur.val;
cur = cur.right;
}
}
// kth largest: same loop with left/right swapped.