133. Find the Kth Smallest Element in a BST

Given a binary search tree and a value k, print the kth smallest value in the tree (1-indexed). The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N). k is given on the next line.

Input: First line contains space-separated level-order tokens describing the BST ('N' marks an absent child). Second line contains the integer k. Output: Print a single integer - the kth smallest value in the BST.

1 <= k <= number of nodes <= 10^5

This exact technique (inorder traversal, stop early) is precisely why a BST is so useful for 'rank-based' queries - the sorted-order property that inorder traversal reveals is the whole reason this problem is easy on a BST but harder on a general binary tree.

Find the kth smallest value stored in a binary search tree. Brute force: Perform a full inorder traversal, collect ALL values into a list, then index directly into position (k-1) - this works but does unnecessary extra work continuing the traversal even after the kth element has already been found. Optimised: Stopping the inorder traversal the MOMENT the running counter reaches k avoids visiting any nodes beyond what's strictly necessary - in the best case (small k), this can be much faster than a full traversal, especially on a large tree.

Perform a standard in-order traversal (left, node, right), which for a binary search tree is guaranteed to visit every node's value in strictly increasing order, and append each value to a list as it's visited. Once the traversal finishes, the k-th smallest value is simply the element at index k-1 of that list. This is a real improvement over brute force because it exploits the BST property to get sorted output for free, avoiding a separate O(n log n) sort, though it still visits and stores every node even when k is small. Time: O(n) Space: O(n)

Simulate an in-order traversal iteratively using an explicit stack: push left children until reaching a null, then pop, visit, and move to the right child, repeating. Keep a counter that decrements on every visit, and stop immediately and return the current node's value the moment the counter hits k, without visiting any further nodes. This avoids materializing the full sorted list, so when k is small the traversal can terminate long before touching every node, and the auxiliary space is bounded by the tree's height rather than its total size. Time: O(h + k) Space: O(h)

Traverse the tree in any order (for example the same level-order structure it was built from), collect every node's value into a list while completely ignoring the binary search tree ordering property, then sort the list and read off the value at index k-1. This is correct for any binary tree at all, not just a BST, but it does unnecessary work by sorting values that a BST already stores in an exploitable sorted order. Time: O(n log n) Space: O(n)

1. Perform an INORDER traversal (left subtree, node, right subtree) - for a BST, this visits every value in strictly ascending order. 2. Keep a counter, incrementing it each time you visit a node during this traversal. 3. The moment the counter reaches k, that node's value is your answer - you can stop the traversal immediately at that point.

Time: O(h + k) in the best implementations - proportional to the height (to reach the first node) plus k (the number of nodes visited before stopping), rather than always O(n). Space: O(h) for the recursion stack (or explicit stack if iterative).

Test with k=1 (the minimum value), k equal to the total node count (the maximum value), a single-node tree, and a tree with 10^5 nodes for performance.

Be ready to mention that if this exact query needs to happen REPEATEDLY on the same BST, augmenting each node with a 'count of nodes in its subtree' (a so-called order-statistics tree) answers each query in O(h) without needing a fresh traversal every time - a strong follow-up optimization to mention.