Kth Smallest Element in a BST

📋

Problem

Imagine you have a sorted collection of numbers stored efficiently in a binary search tree, and you want to quickly find the kth smallest number without flattening the entire tree.

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

The number of nodes in the tree is n, where 1 ≤ n ≤ 10^51 ≤ k ≤ nNode values are unique integers

Edge cases: k equals 1 (smallest element) → returns smallest node valuek equals n (largest element) → returns largest node valueTree with only one node → returns that node's value regardless of k=1

</>

IDE

def kthSmallest(root: Optional[TreeNode], k: int) -> int:public int kthSmallest(TreeNode root, int k)int kthSmallest(TreeNode* root, int k)function kthSmallest(root, k)

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int kthSmallest(TreeNode* root, int k) {
    // Write your solution here
    return 0;
}

function kthSmallest(root, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning default or uninitialized value when traversal is incomplete or k is out of range.✅ Ensure traversal visits nodes and returns elements[k-1] after full or partial traversal.

Wrong: last node valueTraversal does not stop early and returns last visited node instead of k-th.✅ Add early stopping condition when count == k during traversal.

Wrong: off-by-one element (e.g., k+1 or k-1 element)Incorrect indexing due to confusion between 0-based and 1-based indexing.✅ Use zero-based indexing with k-1 or count nodes until count == k.

Wrong: wrong node value in skewed treeTraversal misses nodes in skewed trees due to incorrect recursion or iteration.✅ Ensure traversal visits all nodes including null left or right children properly.

Wrong: TLEFull traversal of large tree without early stopping causes timeout.✅ Implement early stopping in traversal to achieve O(H + k) time complexity.

✓

Test Cases

Try testing your code on trees with only one node or skewed structures.

Consider off-by-one errors and whether your traversal stops early after k elements.

Think about how to avoid traversing the entire tree when k is small.

t1_01basic

Input{"root":[3,1,4,null,2],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

The in-order traversal of the BST is [1,2,3,4]. The 1st smallest element is 1.

💡 Recall that in-order traversal of a BST yields sorted node values.

💡 Use in-order traversal and return the k-th element in the traversal list.

💡 Perform in-order traversal and return elements[k-1].

Why it failed: Returned wrong value for canonical example; likely incorrect traversal or indexing. Fix by ensuring in-order traversal and zero-based indexing with k-1.

✓ Correctly returns the 1st smallest element using in-order traversal.

t1_02basic

Input{"root":[5,3,6,2,4,null,null,1],"k":3}

Expected3

⏱ Performance - must finish in 2000ms

In-order traversal is [1,2,3,4,5,6]. The 3rd smallest element is 3.

💡 In-order traversal visits nodes in ascending order.

💡 Count nodes visited until k-th is reached.

💡 Return the value of the node visited at count k.

Why it failed: Incorrect output due to off-by-one error or incomplete traversal. Fix by correctly counting nodes during in-order traversal and returning the k-th node's value.

✓ Correctly identifies the 3rd smallest element in the BST.

t2_01edge

Input{"root":[1],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

Single node tree; the only node is the 1st smallest.

💡 Consider the simplest tree with one node.

💡 Traversal should return that single node value regardless of k=1.

💡 Return root.val directly if tree has one node and k=1.

Why it failed: Fails single node case; likely assumes multiple nodes or mishandles null children. Fix by handling single node trees correctly in traversal.

✓ Correctly returns the only node value for single-node tree.

t2_02edge

Input{"root":[1,null,2,null,3,null,4,null,5],"k":5}

Expected5

⏱ Performance - must finish in 2000ms

Right skewed tree with nodes 1 to 5; 5th smallest is 5.

💡 Test skewed trees where all nodes are right children.

💡 In-order traversal still visits nodes in ascending order.

💡 Ensure traversal handles skewed structure without missing nodes.

Why it failed: Fails skewed tree; likely stops traversal early or mishandles null left children. Fix by correctly traversing all nodes in skewed trees.

✓ Correctly handles right skewed tree and returns largest node for k=n.

t2_03edge

Input{"root":[5,4,null,3,null,2,null,1],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

Left skewed tree with nodes 1 to 5; smallest is 1.

💡 Test skewed trees where all nodes are left children.

💡 In-order traversal visits left subtree first, then root.

💡 Ensure traversal correctly reaches leftmost node for smallest element.

Why it failed: Fails left skewed tree; likely does not traverse left children fully. Fix by recursively or iteratively traversing left subtree completely.

✓ Correctly returns smallest node in left skewed tree.

t3_01corner

Input{"root":[3,1,4,null,2],"k":2}

Expected2

⏱ Performance - must finish in 2000ms

In-order traversal is [1,2,3,4]. The 2nd smallest element is 2.

💡 Check if your code stops traversal after finding k elements.

💡 Use early stopping in recursive or iterative traversal to improve efficiency.

💡 Return node value immediately when count reaches k during traversal.

Why it failed: Fails to stop early and returns wrong element or last element; fix by adding early stopping condition when count == k.

✓ Correctly implements early stopping and returns the 2nd smallest element.

t3_02corner

Input{"root":[2,1,3],"k":3}

Expected3

⏱ Performance - must finish in 2000ms

In-order traversal is [1,2,3]. The 3rd smallest element is 3.

💡 Beware of off-by-one errors in indexing k-th element.

💡 Remember k is 1-indexed; adjust zero-based indexing accordingly.

💡 Return elements[k-1] if using list, or count nodes until count == k.

Why it failed: Returns wrong element due to off-by-one error; fix by using k-1 index or correct count comparison.

✓ Correctly handles 1-based indexing for k.

t3_03corner

Input{"root":[5,3,6,2,4,null,null,1],"k":4}

Expected4

⏱ Performance - must finish in 2000ms

In-order traversal is [1,2,3,4,5,6]. The 4th smallest element is 4.

💡 Avoid greedy approaches that pick nodes without full traversal.

💡 In-order traversal guarantees sorted order; use it instead of heuristics.

💡 Count nodes visited in order and return the k-th visited node's value.

Why it failed: Fails greedy approach that picks wrong node; fix by performing full or early-stopped in-order traversal.

✓ Correctly uses in-order traversal to find the k-th smallest element.

t4_01performance

Input{"root":[50000,25000,75000,12500,37500,62500,87500,6250,18750,31250,43750,56250,68750,81250,93750,3125,9375,15625,21875,28125,34375,40625,46875,53125,59375,65625,71875,78125,84375,90625,96875,1562,4687,7812,10937,14062,17187,20312,23437,26562,29687,32812,35937,39062,42187,45312,48437,51562,54687,57812,60937,64062,67187,70312,73437,76562,79687,82812,85937,89062,92187,95312,98437,781,2343,3906,5468,7031,8593,10156,11718,13281,14843,16406,17968,19531,21093,22656,24218,25781,27343,28906,30468,32031,33593,35156,36718,38281,39843,41406,42968,44531,46093,47656,49218,50781,52343,53906,55468,57031,58593,60156,61718,63281,64843,66406,67968,69531,71093,72656,74218,75781,77343,78906,80468,82031,83593,85156,86718,88281,89843,91406,92968,94531,96093,97656,99218],"k":100}

Expectednull

⏱ Performance - must finish in 2000ms

Large balanced BST with n=100 nodes; solution must run in O(H + k) or O(n) time within 2 seconds.

💡 Brute force full traversal is O(n) and may be slow for large n.

💡 Use iterative or recursive in-order traversal with early stopping after k nodes.

💡 Avoid building full list; stop traversal once k-th smallest is found.

Why it failed: TLE due to O(n) full traversal or exponential complexity. Fix by implementing early stopping in in-order traversal to achieve O(H + k) time.

✓ Efficient traversal with early stopping confirms O(H + k) complexity.

Practice

1. You need to design an iterator over a binary search tree that returns elements in ascending order, but you want to avoid storing all elements upfront to save space. Which approach best fits this requirement?

easy

A. Use a divide-and-conquer approach to merge sorted lists from left and right subtrees at each next() call.

B. Perform a full inorder traversal upfront and store all elements in a list for O(1) next() calls.

C. Use a breadth-first traversal to visit nodes level by level and return elements in sorted order.

D. Use a controlled inorder traversal with a stack to lazily fetch the next smallest element on demand.

Solution

1. Step 1: Understand the problem constraints

   The iterator must return elements in ascending order without storing all nodes upfront to save space.

2. Step 2: Evaluate approaches

   Full inorder traversal (B) uses O(n) space upfront, breadth-first (C) does not guarantee sorted order, and divide-and-conquer merging (D) is inefficient per next() call. Controlled inorder traversal with a stack (A) lazily fetches the next smallest element using O(h) space, which is optimal for this problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Lazy stack-based inorder traversal matches the problem requirements [OK]

Hint: Lazy stack traversal avoids full storage [OK]

Common Mistakes:

• Thinking BFS returns sorted order
• Assuming full traversal is always best
• Confusing divide-and-conquer with lazy iteration

2. Consider the following code snippet implementing the optimal approach for Two Sum IV in BST. Given the BST with nodes [5,3,6,2,4,null,7] and target k=9, what is the value of variable s during the first iteration of the while loop?

easy

A. 9

B. 5

C. 11

D. 7

Solution

1. Step 1: Perform inorder traversal

   Inorder traversal of BST yields sorted array: [2, 3, 4, 5, 6, 7]

2. Step 2: Calculate s in first iteration

   left=0 (value=2), right=5 (value=7), s = 2 + 7 = 9

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sum matches target k=9 on first iteration [OK]

Hint: Inorder array first + last sum equals target [OK]

Common Mistakes:

• Off-by-one error in indexing left or right
• Confusing node values with indices
• Miscomputing sum s

3. Examine the following code snippet intended to balance a BST by collecting nodes via inorder traversal and rebuilding the tree. Identify the subtle bug that could cause incorrect tree structure or cycles.

medium

A. The left and right pointers of nodes are not reset before rebuilding.

B. The inorder traversal appends nodes instead of values.

C. The middle index calculation uses integer division which may skew balance.

D. The stack is popped instead of dequeued, reversing processing order.

Solution

1. Step 1: Identify pointer reset necessity

   When rebuilding, left and right pointers must be reset to avoid old links causing cycles.

2. Step 2: Locate missing reset in code

   Commented out line resetting node.left and node.right causes bug.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not resetting pointers -> cycles or incorrect tree [OK]

Hint: Always reset node pointers when rebuilding trees [OK]

Common Mistakes:

• Ignoring pointer reset leads to subtle bugs
• Misunderstanding traversal appending nodes is correct
• Thinking stack order affects correctness here

4. What is the time complexity of the optimal iterative algorithm for finding the lowest common ancestor in a BST, where h is the height of the tree and n is the number of nodes?

medium

A. O(log n), assuming the BST is balanced and height h = log n

B. O(n), because in the worst case the algorithm may visit all nodes

C. O(h), since the algorithm traverses from root down to the split point along one path

D. O(1), because the algorithm uses constant space and simple comparisons

Solution

1. Step 1: Identify traversal path length

   The algorithm moves from root down one path until the split point, visiting at most h nodes.

2. Step 2: Understand h vs n

   Height h can be up to n in worst case (skewed tree), but the question asks for optimal algorithm time complexity, which assumes balanced BST where h = log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Traversal limited to one root-to-node path in balanced BST [OK]

Hint: Time depends on tree height, not total nodes [OK]

Common Mistakes:

• Confusing worst-case O(n) with average-case O(log n)
• Assuming constant time due to simple comparisons
• Ignoring that recursion stack space is not used here

5. Suppose the BST can contain duplicate values and the range is inclusive [low, high]. How should the trimming algorithm be modified to correctly handle duplicates without breaking BST properties?

hard

A. Change all comparisons to strict inequalities (e.g., < low to <= low) to exclude duplicates outside range.

B. Rebuild the BST from scratch after filtering duplicates to ensure correct ordering.

C. Adjust pruning conditions to include nodes equal to low or high by using <= and >= comparisons appropriately.

D. Ignore duplicates during pruning since BST properties guarantee uniqueness.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on left or right subtree depending on implementation; inclusive range means nodes equal to low or high must be kept.

2. Step 2: Modify pruning conditions

   Use <= and >= in comparisons to keep nodes equal to boundaries, ensuring duplicates within range remain.

3. Step 3: Avoid rebuilding

   Rebuilding wastes time and space; pruning with adjusted conditions preserves BST and duplicates correctly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Inclusive pruning keeps duplicates at boundaries [OK]

Hint: Use inclusive comparisons to keep duplicates within range [OK]

Common Mistakes:

• Using strict inequalities excludes boundary duplicates
• Rebuilding unnecessarily wastes resources