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

Time Complexity: Kth Smallest Element in BST

O(h + k)

Understanding Time Complexity

We want to know how long it takes to find the kth smallest value in a Binary Search Tree (BST).

This helps us understand how the search time grows as the tree or k grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function kthSmallest(root: TreeNode | null, k: number): number {
  let count = 0;
  let result = -1;

  function inorder(node: TreeNode | null) {
    if (!node || result !== -1) 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: Visits nodes until the kth smallest is found, up to k times in best case, up to n times in worst case.

How Execution Grows With Input

As the tree size (n) grows, the number of nodes visited depends on k and tree shape.

Input Size (n)	Approx. Operations (nodes visited)
10	Up to 10 (if k=10), or fewer if k smaller
100	Up to 100 (if k=100), or fewer if k smaller
1000	Up to 1000 (if k=1000), or fewer if k smaller

Pattern observation: The work grows roughly with k, but cannot exceed n (total nodes).

Final Time Complexity

Time Complexity: O(h + k)

This means the time depends on the tree height (h) plus how many nodes we visit until kth smallest.

Common Mistake

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

[OK] Correct: Actually, we stop once we find the kth smallest, so if k is small, we visit fewer nodes, making it faster than visiting all.

Interview Connect

Understanding this time complexity shows you can analyze recursive tree traversals and how stopping early affects performance.

Self-Check

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