← Create New Paste

Kth Smallest Element in a BST (LeetCode 230): Inorder Traversal and Beyond

3 views
Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed). It is a short problem, but it tests whether you really use the BST property, and the follow-up question is where strong candidates stand out. The key property An inorder traversal (left, node, right) of a BST visits values in sorted order. So the kth node visited in inorder is the answer. Say this first; it is the entire insight. Approach 1: Recursive inorder with early stop def kth_smallest(root, k): count = 0 answer = None def inorder(node): nonlocal count, answer if not node or answer is not None: return inorder(node.left) count += 1 if count == k: answer = node.val return inorder(node.right) inorder(root) return answer Stopping early matters: you visit only about h + k nodes instead of the whole tree. Approach 2: Iterative with a stack def kth_smallest_iter(root, k): stack, node = [], root while stack or node: while node: stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0: return node.val node = node.right Time is O(h + k), space O(h), where h is the tree height. Interviewers often prefer this version because it avoids recursion limits on skewed trees and makes the early exit obvious. A naive answer to avoid Collecting every value into a list and sorting it works, but ignores the BST property and costs O(n log n). Mention it only as a baseline. The classic follow-up "What if the tree is modified often (inserts and deletes) and you need kth smallest frequently?" The strong answer is to augment each node with the size of its subtree. Then: - If the size of the left subtree is k - 1, the current node is the answer. - If it is at least k, go left. - Otherwise, go right with k reduced by left size + 1. Each query becomes O(h), and inserts and deletes update sizes along the path. In a balanced tree, that is O(log n) for everything. This is the idea behind order-statistic trees. Edge cases - k equals 1 (the leftmost node) or k equals the number of nodes (the rightmost). - A completely skewed tree, where h equals n. - Duplicates, if allowed, depend on how the BST places equal values; ask the interviewer. How to present it State the inorder property, write the iterative version, trace a small tree with k = 3, then volunteer the subtree-size augmentation for the follow-up. If you blank on the stack loop under pressure, Linkjob AI (https://linkjob.ai) offers real-time help during live technical interviews, quietly reminding you of the pattern while you explain your reasoning in your own words.
Created Nov 17, 2026 21:32 Expires Nov 17, 2027 21:32