Log inSign up
mediumLeetCodeNot Started

Kth Smallest Element in a BST

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

Given the root of a binary search tree, and an integer k, return the `k`-th smallest value (1-indexed) of all the values of the nodes in the tree.

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 104
  • 0 <= Node.val <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why BST inorder sequence is monotonically non-decreasing.
  • Implement the iterative stack-based inorder traversal with early termination.
  • Analyze follow-up optimizations using augmented subtree size counts.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find k-th smallest in BST.
  • Sorted order retrieval from tree.
  • Early exit after k steps.

Algorithmic Decision Tree:

  • Iterative stack inorder traversal: push left spine.
  • Pop node, decrement k. If k == 0, return curr.val.

Connected Patterns:

Kth Largest Element in a BSTBinary Search Tree IteratorValidate Binary Search Tree

1. Full Inorder Array Collection

Intuition

Traverse the entire BST using inorder DFS, appending each visited node's value into a list. Return the element at index k - 1.

When to apply: Simple baseline approach when memory is unrestricted.

Algorithm

  1. Collect all elements in an array via recursive inorder DFS and return index k - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 void inorder(TreeNode* root, std::vector<int>& vals) {
13 if (!root) return;
14 inorder(root->left, vals);
15 vals.push_back(root->val);
16 inorder(root->right, vals);
17 }
18public:
19 int kthSmallest(TreeNode* root, int k) {
20 std::vector<int> vals;
21 inorder(root, vals);
22 return vals[k - 1];
23 }
24};
25
26int main() {
27 TreeNode* root = new TreeNode(5);
28 root->left = new TreeNode(3);
29 root->right = new TreeNode(6);
30 root->left->left = new TreeNode(2);
31 root->left->right = new TreeNode(4);
32 root->left->left->left = new TreeNode(1);
33
34 Solution sol;
35 std::cout << "3rd smallest: " << sol.kthSmallest(root, 3) << std::endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)

2. Recursive Inorder DFS with Early Exit

Intuition

Maintain global/closure counter count and ans. Inorder DFS visits left, then checks curr: decrement k. If k == 0, set ans = curr.val and stop further traversal.

When to apply: When writing concise recursion without allocating array memory.

Algorithm

  1. Run recursive DFS in ascending order, decrementing counter k. Terminate recursion when counter hits 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11 int count = 0;
12 int ans = -1;
13
14 void inorder(TreeNode* root, int k) {
15 if (!root || count >= k) return;
16
17 inorder(root->left, k);
18
19 count++;
20 if (count == k) {
21 ans = root->val;
22 return;
23 }
24
25 inorder(root->right, k);
26 }
27public:
28 int kthSmallest(TreeNode* root, int k) {
29 count = 0;
30 ans = -1;
31 inorder(root, k);
32 return ans;
33 }
34};
35
36int main() {
37 TreeNode* root = new TreeNode(5);
38 root->left = new TreeNode(3);
39 root->right = new TreeNode(6);
40 root->left->left = new TreeNode(2);
41 root->left->right = new TreeNode(4);
42 root->left->left->left = new TreeNode(1);
43
44 Solution sol;
45 std::cout << "3rd smallest: " << sol.kthSmallest(root, 3) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(H + k) where H is tree height
  • Space complexity: O(H) recursion stack space

3. Iterative Stack Inorder Traversal

Intuition

1. Maintain an explicit stack of TreeNode pointers. 2. Push the entire left branch of the tree onto the stack until curr == null. 3. Pop the top node from the stack. This is the next smallest node in inorder sequence. 4. Decrement k. If k == 0, return curr.val. 5. Move curr = curr.right and repeat. This achieves strictly O(H + k) runtime and O(H) stack space.

When to apply: The standard gold standard for interviews; provides clean control flow without recursion overhead.

Algorithm

  1. Simulate inorder traversal using an explicit stack; pop and decrement k until k == 0.

Iterative Stack Inorder Traversal Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Stack is now [5, 3, 2, 1]
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
curr starts at 5. Push 5, 3, 2, 1 to stack.
Decision / next transition
1
Why this step matters

Stack is now [5, 3, 2, 1].

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 int kthSmallest(TreeNode* root, int k) {
14 std::stack<TreeNode*> st;
15 TreeNode* curr = root;
16
17 while (curr || !st.empty()) {
18 while (curr) {
19 st.push(curr);
20 curr = curr->left;
21 }
22
23 curr = st.top();
24 st.pop();
25
26 k--;
27 if (k == 0) return curr->val;
28
29 curr = curr->right;
30 }
31
32 return -1;
33 }
34};
35
36int main() {
37 TreeNode* root = new TreeNode(5);
38 root->left = new TreeNode(3);
39 root->right = new TreeNode(6);
40 root->left->left = new TreeNode(2);
41 root->left->right = new TreeNode(4);
42 root->left->left->left = new TreeNode(1);
43
44 Solution sol;
45 std::cout << "3rd smallest: " << sol.kthSmallest(root, 3) << std::endl;
46 return 0;
47}

Time & Space Complexity

  • Time complexity: O(H + k) where H is tree height
  • Space complexity: O(H) explicit stack space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Full Inorder Array CollectionO(N)O(N)Collect all elements in an array via recursive inorder DFS and return index k - 1.O(N)
2.Recursive Inorder DFS with Early ExitO(H + k) where H is tree heightO(H) recursion stack spaceRun recursive DFS in ascending order, decrementing counter k. Terminate recursion when counter hits 0.O(H + k) where H is tree height
3.Iterative Stack Inorder TraversalOptimalO(H + k) where H is tree heightO(H) explicit stack spaceSimulate inorder traversal using an explicit stack; pop and decrement k until k == 0.O(H + k) where H is tree height

Common Pitfalls & Crucial Edge Cases

Returning `vals[k]` instead of `vals[k - 1]`

Off-by-one error since k is 1-indexed.

Traversing right before left

Traverses in descending order instead of ascending order.

Stack overflow in deep recursion

For large trees (N = 104), recursion can exceed stack limits, making iterative stack preferred.

Crucial Edge Cases to Validate:

  • k = 1 — Returns the minimum element (leftmost node) in O(H) time.
  • k = N — Traverses all nodes and returns the maximum element (rightmost node).
  • Single node tree (N = 1, k = 1) — Returns the root node immediately.
  • Left-skewed tree — Stack holds all N nodes and pops them in order.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the standard iterative stack solution first (O(H + k) time, O(H) space).
  2. Proactively answer the LeetCode Follow-Up question: 'If tree is modified often with inserts/deletes, augment nodes with subtree size to achieve O(H) queries.'
  3. Emphasize that the stack height is bounded by H = O(log N) on balanced trees.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the Order Statistic Tree approach optimize frequent k-th smallest queries when insertions and deletions happen often?

2.What is the maximum number of nodes pushed onto the stack at any one time in the iterative approach?

3.If k = 1, how many nodes does the iterative approach visit?

Back to DSA Sheet