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. Consider the following code for computing the range sum of a BST. Given the BST with root value 10, left child 5, right child 15, and range [7, 15], what is the final value of total returned by rangeSumBST?

easy

A. 25

B. 15

C. 40

D. 30

Solution

1. Step 1: Trace initial stack and total

   Start with stack=[10], total=0.

2. Step 2: Pop 10 (in range), add 10, push left(5) and right(15)

   total=10, stack=[5,15]

3. Step 3: Pop 15 (in range), add 15, push left(null) and right(null)

   total=25, stack=[5,null,null]

4. Step 4: Pop null (skip), then pop null (skip), then pop 5 (less than low=7), push right(null)

   total=25, stack=[null]

5. Step 5: Pop null (skip), stack empty, return total=25

   5 is less than low, so it is skipped and not added.

6. Final Answer:

   Option A -> Option A

7. Quick Check:

   Sum includes 10 and 15 only, total=25 [OK]

Hint: Only nodes within [7,15] add to total [OK]

Common Mistakes:

• Adding nodes outside range
• Forgetting to push children after adding node

2. The following code attempts to find the lowest common ancestor in a BST. Identify the bug that causes incorrect results when one node is ancestor of the other.

def lowestCommonAncestor(root, p, q):
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current

medium

A. Line 3: Using '<=' and '>=' instead of '<' and '>' causes incorrect ancestor detection.

B. Line 6: Returning current too early without checking if current matches p or q.

C. Line 4: Not handling null root before loop causes crash on empty tree.

D. Line 5: Moving current to left or right without verifying if child exists causes errors.

Solution

1. Step 1: Analyze comparison operators

   Using '<=' and '>=' causes the loop to move past the node when p or q equals current, missing the case where current is ancestor of itself.

2. Step 2: Correct operator usage

   Changing to '<' and '>' ensures the loop stops at the correct ancestor node, including when one node is ancestor of the other.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Inclusive comparisons skip valid ancestor nodes [OK]

Hint: Use strict inequalities to detect ancestor nodes correctly [OK]

Common Mistakes:

• Assuming ancestor must be strictly above nodes
• Ignoring null root edge cases
• Returning too early without validation

3. What is the time and space complexity of the optimal inorder traversal BST validation algorithm for a tree with n nodes and height h?

medium

A. Time O(n), Space O(h) due to recursion stack where h is tree height

B. Time O(n log n), Space O(n) due to storing all nodes

C. Time O(n^2), Space O(1) because no extra data structures are used

D. Time O(n), Space O(n) because all nodes are stored during traversal

Solution

1. Step 1: Identify time complexity

   The algorithm visits each node exactly once in inorder traversal, so time is O(n).

2. Step 2: Identify space complexity

   Space is O(h) due to recursion stack, where h is the height of the tree; no extra arrays store all nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and stack space proportional to tree height [OK]

Hint: Inorder traversal visits each node once, stack depth = tree height [OK]

Common Mistakes:

• Confusing recursion stack space with storing all nodes
• Assuming O(n log n) due to sorting
• Ignoring recursion stack space

4. The following code attempts to validate a BST using inorder traversal. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line checking if node is null (if not node: return true)

B. Line updating prev[0] = node.val

C. Line comparing node.val < prev[0] instead of node.val <= prev[0]

D. Line calling inorder(node.left)

Solution

1. Step 1: Identify BST strict inequality

   BST requires node.val to be strictly greater than previous inorder value; using < instead of <= allows duplicates.

2. Step 2: Understand impact of bug

   Using node.val < prev[0] misses the case when node.val == prev[0], incorrectly allowing duplicates and invalid BSTs.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Strict inequality check is essential to reject duplicates [OK]

Hint: BST nodes must be strictly increasing in inorder traversal [OK]

Common Mistakes:

• Allowing duplicates by using < instead of <=
• Not resetting prev between calls
• Only comparing immediate children

5. Suppose the BST nodes can have duplicate values and you want to compute the sum of all nodes within [low, high], including duplicates. Which modification to the iterative DFS with pruning approach correctly handles duplicates without losing efficiency?

hard

A. Use a hash set to track visited nodes to avoid double counting duplicates.

B. Remove pruning and traverse all nodes to ensure duplicates are counted.

C. Keep pruning logic unchanged since BST property guarantees duplicates are on one side only.

D. Modify pruning to include equal values on both left and right subtrees when node.val equals low or high.

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can be on either left or right subtree depending on insertion rules, so pruning must consider equality carefully.

2. Step 2: Adjust pruning for duplicates

   When node.val equals low or high, both subtrees may contain duplicates within range, so both should be explored.

3. Step 3: Avoid removing pruning entirely

   Removing pruning loses efficiency; using a hash set is unnecessary as nodes are unique objects.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Pruning adjusted for equality handles duplicates efficiently [OK]

Hint: Include equal values on both sides when pruning [OK]

Common Mistakes:

• Removing pruning loses efficiency
• Assuming duplicates only on one side