Kth smallest / Kth largest element in a BST
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
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.