The challenge
Return the kth smallest key of a strict BST, using one-based k.
Return None/nullopt for nonpositive k or k larger than the node count.
Example
k = 3 returns 6. The seven-node example has no ninth smallest key.
Use the walkthrough below to inspect the input and each state change.
See Kth smallest, step by step
Follow the branches. Watch the state change.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | 8 | B | C | — |
| B | 4 | D | E | — |
| C | 12 | F | G | — |
| D | 2 | null | null | — |
| E | 6 | null | null | — |
| F | 10 | null | null | — |
| G | 14 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:8View original input
A:8 [L:B, R:C] · B:4 [L:D, R:E] · C:12 [L:F, R:G] · D:2 [L:null, R:null] · E:6 [L:null, R:null] · F:10 [L:null, R:null] · G:14 [L:null, R:null]
k = 3
Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.
Put it into code
Inorder visits keys in increasing order, so stop on the kth visit.
Nodes store value, left, and right. C++ uses C++17 or later.
from collections import deque
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def kth_smallest(root, k):
if k <= 0:
return None
stack, node = [], root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
k -= 1
if k == 0:
return node.value
node = node.right
return None
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
optional<long long> kth_smallest(Node* root, int k) {
if (k <= 0) return nullopt;
stack<Node*> pending;
Node* node = root;
while (node || !pending.empty()) {
while (node) { pending.push(node); node = node->left; }
node = pending.top(); pending.pop();
if (--k == 0) return node->value;
node = node->right;
}
return nullopt;
}