Kth Smallest Element in BST in DSA Go - 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).

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    current := root
    count := 0

    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        if count == k {
            return current.Val
        }
        current = current.Right
    }
    return -1
}
    

This code finds the kth smallest element by doing an in-order traversal using a stack.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: In-order traversal visiting nodes one by one.
• How many times: Up to k nodes are visited before stopping.

How Execution Grows With Input

As k grows, the number of nodes visited grows roughly the same.

Input Size (n)	Approx. Operations (visits)
10, k=3	3
100, k=50	50
1000, k=700	700

Pattern observation: The work grows linearly with k, not necessarily with total n.

Final Time Complexity

Time Complexity: O(h + k)

This means the time depends on the tree height plus how many nodes we visit up to k.

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 often we visit fewer than all nodes.

Interview Connect

Understanding this helps you explain how tree structure affects search speed and shows you can analyze partial traversals.

Self-Check

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