Mar 18, 2026 📖 4 min read

Last updated on Apr 2, 2026

Kth Smallest Element in a BST — Coding Interview Walkthrough

Q: What specific binary search tree property solves the Kth Smallest Element naturally?

An Inorder Traversal inherently processes binary search tree nodes in absolute strictly sorted ascending order. By processing the left child, then the root, then the right child, you can accurately count up to K without organizing a secondary data structure.

Q: Can you decrease the time complexity if the BST is frequently modified?

If insertion and deletion operations frequently occur, a standard O(N) traversal bottlenecks. By modifying the fundamental BST nodes to store the size of their left subtrees, you enable O(log N) random access to immediately jump to the Kth element without iterating sequentially.

By intervu.dev

Hero Image for Kth Smallest Element in a BST — Coding Interview Walkthrough

The core approach: Kth Smallest Element in a BST is solved with in-order DFS in O(n) time and O(h) space. In-order traversal visits BST nodes in ascending order. Count nodes as they are visited; when the count reaches k, the current node holds the answer. An iterative approach with an explicit stack avoids recursion depth issues.

You’re in a coding interview. The interviewer says: “Find the kth smallest element in a BST.” The answer comes straight from one property of BSTs: in-order traversal visits nodes in ascending sorted order. The kth node visited in-order is the kth smallest. This is really a test of whether you know your BST traversal cold.

Already know how to solve Kth Smallest Element In A Bst? Try a Kth Smallest Element In A Bst mock interview on Intervu →

The Problem

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all node values.

Example

Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
BST in-order property	Do you immediately connect “kth smallest” to in-order traversal?
Early termination	Do you stop after k nodes, not traverse the whole tree?
Iterative vs. recursive	Can you implement both? Iterative is preferred for early exit.
Follow-up: frequent reads	Do you know the augmented-tree approach for O(log n) queries?

Step 1: Clarifying Questions

Is k always valid? Yes — 1 <= k <= number of nodes.
Are node values unique? Yes — BST nodes have distinct values.

Step 2: The Key Insight

In-order traversal of a BST visits nodes in ascending sorted order. The kth node visited is the kth smallest. No sorting required — the BST structure gives you sorted order for free.

BST [5,3,6,2,4,null,null,1] with in-order traversal annotations showing visit order 1st through 6th. Node 3 (k=3) is highlighted.

---

Step 3: Algorithm

Use an explicit stack for iterative in-order traversal. Push left nodes until null, then pop and visit, decrement k, push right child. Stop when k == 0.

Python Implementation

Iterative (preferred — cleanest early exit):

def kthSmallest(root, k: int) -> int:
    stack = []
    current = root

    while current or stack:
        while current:
            stack.append(current)
            current = current.left

        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val

        current = current.right

Time & Space Complexity

Aspect	Complexity
Time	O(H + k) — H is tree height, stop after k nodes
Space	O(H) — stack depth

Common Interview Mistakes

Traversing the whole tree. Stop as soon as k hits 0. No need to visit remaining nodes.
Collecting all values then indexing. values[k-1] works but is O(n) time and space. The iterative approach terminates early.
Not knowing the follow-up. If the BST is modified frequently and kthSmallest is called many times, augment each node with left_count. Query becomes O(log n).

What a Strong Candidate Sounds Like

“In-order traversal of a BST visits nodes in ascending order, so I want the kth node visited. I’ll use an iterative approach with an explicit stack — push lefts, pop and count, move right. I stop the moment k hits zero. Time is O(H + k), space O(H).”

Example Interview Dialogue

Interviewer: What if this is called millions of times on a frequently updated BST?

Candidate: I’d augment each node with the count of nodes in its left subtree. On insert or delete, update counts along the path — O(log n). On query, binary-search: if k == left_count + 1 the current node is the answer; if k <= left_count go left; else go right with k = k - left_count - 1. Each query becomes O(log n).

Validate Binary Search Tree — In-order produces sorted sequence; use to validate.
Lowest Common Ancestor of a BST — BST path properties for LCA.
Invert Binary Tree — Tree traversal fundamentals.

Frequently Asked Questions

What specific binary search tree property solves the Kth Smallest Element naturally?