Skip to content

Kth Smallest Inorder

The Connection You Need to Internalize

Here is the single most important fact about BSTs:

Inorder traversal of a BST produces values in sorted order.

If you have this tree:

        5
       / \
      3   7
     / \ / \
    2  4 6  8

Inorder traversal visits: left subtree, then root, then right subtree. That gives: 2, 3, 4, 5, 6, 7, 8. Sorted.

This isn't a coincidence. The BST property guarantees it. Everything in the left subtree is smaller than the root — so it comes first. Everything in the right subtree is larger — so it comes last. Apply this reasoning recursively at every node, and you get sorted order.

Once you see this connection, a whole class of problems becomes trivial: "find the kth smallest," "find the next element," "find the previous element" — they all reduce to walking the inorder sequence.

Kth Smallest Element (LC 230)

Problem: Given a BST and an integer \(k\), return the \(k\)th smallest element (1-indexed).

Since inorder = sorted order, the \(k\)th smallest element is just the \(k\)th node visited in an inorder traversal. You don't need to collect all values into an array. Just count as you traverse and stop at \(k\).

The iterative inorder traversal from Chapter 2 is perfect here because you can stop early — no need to visit all \(n\) nodes if \(k\) is small.

Iterative inorder traversal uses a stack to visit nodes in sorted order

Full Trace: \(k = 3\)

        5
       / \
      3   7
     / \ / \
    2  4 6  8
Step Action Stack (top → bottom) Current Count
1 Push down left [5, 3, 2] nullptr 0
2 Pop 2, count++ [5, 3] 2 1
3 2 has no right child [5, 3] nullptr 1
4 Pop 3, count++ [5] 3 2
5 3 has right child 4, push down left [5, 4] nullptr 2
6 Pop 4, count++ [5] 4 3 = k

Count hits \(k = 3\) at node 4. Return 4.

Verify: sorted order is 2, 3, 4, 5, 6, 7, 8. The 3rd element is 4. Correct.

The Code

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> nodeStack;
    TreeNode* current = root;
    int count = 0;

    while (current || !nodeStack.empty()) {
        while (current) {
            nodeStack.push(current);
            current = current->left;
        }
        current = nodeStack.top();
        nodeStack.pop();
        count++;
        if (count == k) return current->value;
        current = current->right;
    }
    return -1;
}

This is the standard iterative inorder traversal with one added line: check if count == k and return early.

Complexity: \(O(h + k)\) time — we descend \(h\) levels to reach the leftmost node, then visit \(k\) nodes. \(O(h)\) space for the stack.

Order-statistic tree augments each node with left subtree size for O(log n) rank queries

Augmented BSTs: O(log n) Rank Queries

The iterative approach takes \(O(h + k)\). If \(k\) is close to \(n\) and the tree is balanced, that's \(O(n)\). Can we do better?

Yes — if we augment each node with the size of its left subtree. This is called an order-statistic tree.

          5 [3]
         / \
    [1] 3   7 [1]
       / \ / \
  [0] 2  4 6  8 [0]
      [0]  [0]

The number in brackets is leftSize — how many nodes are in that node's left subtree.

To find the \(k\)th smallest:

  • If \(k = \text{leftSize} + 1\): the current node IS the answer (there are exactly \(k-1\) nodes before it).
  • If \(k \leq \text{leftSize}\): the answer is in the left subtree. Recurse left with the same \(k\).
  • If \(k > \text{leftSize} + 1\): the answer is in the right subtree. Recurse right with \(k' = k - \text{leftSize} - 1\).

Trace: \(k = 5\)

Start at 5, leftSize = 3.

Node leftSize k Decision
5 3 5 \(5 > 3 + 1 = 4\) → go right, \(k' = 5 - 3 - 1 = 1\)
7 1 1 \(1 \leq 1\) → go left, \(k' = 1\)
6 0 1 \(1 = 0 + 1\) → found

Answer: 6. Verify: sorted order position 5 is 6. Correct.

Each step goes one level down — \(O(\log n)\) for a balanced tree. The trade-off: you need to maintain leftSize during insertions and deletions. Every insert/delete updates the sizes along the path from root to the modified node.

Inorder Successor (LC 285)

Problem: Given a BST and a target node, find the node with the smallest value greater than the target. This is the inorder successor — the next element in sorted order.

Two cases:

Case 1: The target has a right child. The successor is the leftmost node in the right subtree. Go right once, then go left as far as possible.

Case 2: The target has no right child. The successor is the nearest ancestor for which the target is in its left subtree. Think about it — if you're in someone's left subtree, that someone comes right after you in inorder.

You can handle both cases with a single top-down search from the root:

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* target) {
    TreeNode* successor = nullptr;
    while (root) {
        if (root->value > target->value) {
            successor = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return successor;
}

When you move left, the current node might be the successor — record it. When you move right, the current node is too small — skip it. The last recorded candidate is the answer.

Trace: Successor of 4

        5
       / \
      3   7
     / \ / \
    2  4 6  8
Step Node Target = 4 Action Candidate
1 5 \(5 > 4\) Record 5, go left 5
2 3 \(3 \leq 4\) Go right 5
3 4 \(4 \leq 4\) Go right 5
4 nullptr — Stop 5

Successor of 4 is 5. Correct — in sorted order 2, 3, 4, **5**, 6, 7, 8.

Inorder predecessor is the mirror: record when you go right, skip when you go left.

Complexity: \(O(h)\) time, \(O(1)\) space.

Try It

The starter code asks for the 3rd smallest element in a 6-node BST.

Predict before running: The tree has values 2, 3, 4, 5, 6, 7. The 3rd smallest is 4.

Challenge: What is the inorder successor of the largest element in the BST? Trace through inorderSuccessor for target = 8 in our example tree. (Answer: successor is never updated, returns nullptr.)

Challenge 2: Implement kthLargest — the \(k\)th largest element. You have two options: do a reverse inorder (right, root, left), or compute \(k' = n - k + 1\) and call kthSmallest. Which is simpler if you don't know \(n\)?

Edge Cases to Watch For

  • 0-indexed vs 1-indexed \(k\): The problem uses 1-indexed \(k\). If you accidentally use 0-indexed counting (count == k - 1), you return the wrong element. Always match your counter initialization and comparison to the problem's indexing.
  • \(k\) is out of range (\(k > n\) or \(k \leq 0\)): The code returns \(-1\) when the loop ends without finding the \(k\)th element. If the problem does not guarantee valid \(k\), you need this guard — otherwise you silently return a sentinel that could be mistaken for a real value.

Problems

Problem Link Difficulty
LC 230 — Kth Smallest Element in a BST leetcode.com/problems/kth-smallest-element-in-a-bst Medium
LC 285 — Inorder Successor in BST leetcode.com/problems/inorder-successor-in-bst Medium
LC 538 — Convert BST to Greater Tree leetcode.com/problems/convert-bst-to-greater-tree Medium