Kth Smallest Element in BST in DSA C++

Mental Model

A binary search tree keeps smaller values on the left and bigger on the right, so the smallest values appear first if we look from left to right.

Analogy: Imagine a sorted bookshelf where smaller books are on the left and bigger books on the right. To find the kth smallest book, you start from the left and count until you reach the kth one.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑ (root)

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find 3rd smallest element

Goal: Find the 3rd smallest value in the BST by visiting nodes in order

Step 1: Go left from 5 to 3

5 -> [3 ↑] -> 7 -> 2 -> 4 -> 8

Why: Left subtree has smaller values, so start there

Step 2: Go left from 3 to 2

5 -> 3 -> 7 -> [2 ↑] -> 4 -> 8

Why: Keep going left to find smallest values

Step 3: Visit 2 (1st smallest), move up to 3

5 -> [3 ↑] -> 7 -> 2 -> 4 -> 8

Why: 2 is smallest, next is parent 3

Step 4: Visit 3 (2nd smallest), go right to 4

5 -> 3 -> 7 -> 2 -> [4 ↑] -> 8

Why: After visiting 3, check right child for next smallest

Step 5: Visit 4 (3rd smallest), stop

5 -> 3 -> 7 -> 2 -> 4 -> 8

Why: Found the 3rd smallest element

Result:

2 -> 3 -> 4 -> ... (3rd smallest is 4)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    int count = 0;
    int result = -1;

    void inorder(TreeNode* root, int k) {
        if (!root || result != -1) return; // stop if found or no node
        inorder(root->left, k); // go left to smaller values
        count++;
        if (count == k) {
            result = root->val; // found kth smallest
            return;
        }
        inorder(root->right, k); // go right to bigger values
    }

public:
    int kthSmallest(TreeNode* root, int k) {
        count = 0;
        result = -1;
        inorder(root, k);
        return result;
    }
};

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->right = new TreeNode(8);

    Solution sol;
    int k = 3;
    cout << sol.kthSmallest(root, k) << "\n";
    return 0;
}

if (!root || result != -1) return; // stop if found or no node

stop traversal if no node or kth smallest found

inorder(root->left, k); // go left to smaller values

traverse left subtree first to get smaller values

count++;

increment count when visiting a node

if (count == k) { result = root->val; return; }

check if current node is kth smallest and save result

inorder(root->right, k); // go right to bigger values

traverse right subtree after left and current node

Output

4

Complexity Analysis

Time: O(h + k) because we traverse down the tree height h and visit k nodes in order

Space: O(h) due to recursion stack for tree height h

vs Alternative: Naive approach sorts all nodes O(n log n), this uses BST property to stop early at kth node

Edge Cases

k is 1 (smallest element)

Returns the leftmost node value

DSA C++

if (count == k) { result = root->val; return; }

k equals number of nodes (largest element)

Returns the rightmost node value after full traversal

DSA C++

if (count == k) { result = root->val; return; }

k is larger than number of nodes

Returns -1 as result remains unchanged

DSA C++

if (!root || result != -1) return;

When to Use This Pattern

When asked for the kth smallest or largest in a BST, use inorder traversal because it visits nodes in sorted order.

Common Mistakes

Mistake: Not stopping traversal after finding kth smallest, causing unnecessary work
Fix: Add a check to stop recursion once kth smallest is found

Mistake: Using preorder or postorder traversal which does not guarantee sorted order
Fix: Use inorder traversal to get nodes in ascending order

Summary

Finds the kth smallest value in a binary search tree using inorder traversal.

Use when you need the kth smallest element efficiently without sorting all nodes.

The key insight is that inorder traversal of BST visits nodes in ascending order.