Kth Smallest Element in BST in DSA C++ - Time & Space Complexity

Time Complexity: Kth Smallest Element in BST

O(h + k)

Understanding Time Complexity

We want to understand how the time needed to find the kth smallest element in a Binary Search Tree changes as the tree grows.

How does the number of steps grow when the tree has more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int count = 0;
int result = -1;
bool found = false;

void inorder(TreeNode* root, int k) {
    if (!root || found) return;
    inorder(root->left, k);
    if (found) return;
    count++;
    if (count == k) {
        result = root->val;
        found = true;
        return;
    }
    inorder(root->right, k);
}

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

This code does an in-order traversal of the BST to find the kth smallest element by counting nodes visited.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive in-order traversal visiting nodes.
• How many times: Visits nodes until the kth smallest is found, up to k nodes.

How Execution Grows With Input

As the tree grows, the traversal visits nodes in order until it reaches the kth smallest.

Input Size (n)	Approx. Operations
10	Up to k nodes visited (k ≤ 10)
100	Up to k nodes visited (k ≤ 100)
1000	Up to k nodes visited (k ≤ 1000)

Pattern observation: The number of steps grows roughly with k, not necessarily with total nodes n.

Final Time Complexity

Time Complexity: O(h + k)

This means the time depends on the tree height h plus the number of nodes k we visit to find the kth smallest.

Common Mistake

[X] Wrong: "The time is always O(n) because we might visit all nodes."

[OK] Correct: We stop as soon as we find the kth smallest, so we usually visit fewer than all nodes, especially if k is small.

Interview Connect

Understanding this time complexity helps you explain how tree shape and k affect performance, a key skill in coding interviews.

Self-Check

"What if the BST is balanced versus completely skewed? How would the time complexity change?"