PPractick

The problem

A ranking service stores scores in a BST and gets queries like "what's the 3rd lowest score?" and "what's the 3rd highest?". An inorder traversal visits BST keys in ascending order, so the k-th node it visits is the k-th smallest. A reverse inorder traversal (right, node, left) visits keys in descending order, so its k-th node is the k-th largest. An iterative traversal with a stack can stop as soon as it reaches the k-th node instead of traversing everything.

Example: BST [5, 3, 6, 2, 4, null, null, 1], k = 3 → smallest 3, largest 4.

Function signature

int kthSmallest(TreeNode* root, int k);   // 1 <= k <= n
int kthLargest(TreeNode* root, int k);

Test cases

Input (tree, k)	Output	Explanation
([5, 3, 6, 2, 4, null, null, 1], 3)	smallest 3 largest 4	Sorted: 1 2 3 4 5 6
([5, 3, 6, 2, 4, null, null, 1], 6)	smallest 6 largest 1	k = n
([3, 1, 4, null, 2], 1)	smallest 1 largest 4
([3, 1, 4, null, 2], 4)	smallest 4 largest 1
([7], 1)	smallest 7 largest 7

(Confirm: 1 ≤ k ≤ number of nodes; keys are distinct.)

How interviewers phrase it

• "Given the root of a BST and an integer k, return the kth smallest value" (LeetCode 230), plus "and the kth largest" (GeeksforGeeks).

Clarifying questions to ask

1. Is k 1-indexed? (Yes.)
2. Is k always valid? (Yes.)
3. How often is the tree modified between queries? (That matters for the follow-up.)

Follow-ups to expect

1. "Why inorder?"
2. "Why iterative?"
3. "And the k-th largest?"
4. "Frequent queries with inserts and deletes?"
5. "Complexity?"

Related questions

• Merge 2 BST's Hard
• Correct BST with two nodes swapped Hard
• Insert a given node in BST Medium
• Delete a node in BST Medium
• Check if a tree is a BST or not Medium
• LCA in BST Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in