Kth Smallest Element in BST in DSA Javascript - Time & Space Complexity

Time Complexity: Kth Smallest Element in BST

O(k)

Understanding Time Complexity

We want to understand how long it takes to find the kth smallest value in a binary search tree (BST).

Specifically, how the time grows as the tree size or k changes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function kthSmallest(root, k) {
  let count = 0;
  let result = null;

  function inorder(node) {
    if (!node || result !== null) return;
    inorder(node.left);
    count++;
    if (count === k) {
      result = node.val;
      return;
    }
    inorder(node.right);
  }

  inorder(root);
  return result;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive in-order traversal visiting nodes.
• How many times: Up to k nodes visited before stopping early.

How Execution Grows With Input

As k grows, the number of nodes visited grows roughly linearly up to k.

Input Size (n)	Approx. Operations (nodes visited)
10 (k=3)	3
100 (k=50)	50
1000 (k=900)	900

Pattern observation: The work grows roughly in proportion to k, not the total tree size n.

Final Time Complexity

Time Complexity: O(k)

This means the time to find the kth smallest element grows linearly with k, the position we want.

Common Mistake

[X] Wrong: "The time depends only on the total number of nodes n in the tree."

[OK] Correct: Because the traversal stops once the kth element is found, so time depends mostly on k, not n.

Interview Connect

Understanding this helps you explain how partial traversal can save time compared to visiting the whole tree.

This skill shows you can analyze and optimize tree operations thoughtfully.

Self-Check

"What if the BST is balanced and we keep track of subtree sizes? How would the time complexity change?"