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.