Reviewed by Aditya Kumar · Last reviewed 2026-03-24
**Why BST Kth Smallest:** In-order traversal yields sorted order. kth smallest = kth node in in-order. Used in top-K from sorted structure, percentile queries. **Approach:** (1) In-order with counter: O(h + k) time. (2) Augmented BST: each node stores subtree size—O(h) search...
This easy-level Python/Coding question appears frequently in data engineering interviews at companies like Expedia. While less common, it tests deeper understanding that distinguishes strong candidates.
Start by clearly defining the core concept being asked about. Interviewers want to see that you understand the fundamentals before diving into implementation details. Structure your answer with a definition, then explain the practical application with a concise example.
Why BST Kth Smallest: In-order traversal yields sorted order. kth smallest = kth node in in-order. Used in top-K from sorted structure, percentile queries.
Approach: (1) In-order with counter: O(h + k) time. (2) Augmented BST: each node stores subtree size—O(h) search by comparing k with left size.
Scalability: BST in-memory; for disk-backed (B-tree), similar logic. In data eng: approximate with reservoir sampling or partial sort for top-K from unsorted.
def kth_smallest(root, k):
stack = []
while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0: return root.val
root = root.right
Red Flag: Full in-order then index (wastes memory). Pro-Move: 'Iterative with stack—stops at kth; we use same pattern for kth percentile from sorted column.'
Some links below are affiliate links. If you buy through them we may earn a small commission at no extra cost to you — it helps keep DataEngPrep free.
According to DataEngPrep.tech, this is one of the most frequently asked Python/Coding interview questions, reported at 1 company. DataEngPrep.tech maintains an editor-reviewed database of 1,863 data engineering interview questions across 7 categories.