Kth Smallest Element in a BST

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed).

Function signature

func KthSmallest(root *TreeNode, k int) int

Inputs / outputs

• root: root of the BST.
• k: 1-indexed rank.
• Return: the k-th smallest value.

Example

    3
   / \
  1   4
   \
    2
k = 1
Output: 1

Constraints

• 1 <= number of nodes <= 100_000
• 1 <= k <= number of nodes

Core idea (near-solution)

Inorder traversal of a BST visits nodes in ascending order. Count nodes as you traverse; the k-th visited is the answer.

Invariant: before visiting a node, all nodes in its left subtree are smaller and already counted.

Algorithm (step-by-step)

1. Use an explicit stack for iterative inorder.
2. Walk left as far as possible, pushing nodes.
3. Pop a node, decrement k. If k == 0, return its value.
4. Move to the right child and repeat.

Correctness sketch

• Invariant: before visiting a node, all nodes in its left subtree are smaller and already counted.
• Inorder traversal of a BST yields values in sorted order.
• The stack simulates inorder traversal without recursion.
• Thus each popped node is the next smallest element.

Trace (hand walkthrough)

Example input:
    3
   / \
  1   4
   \
    2
k = 1
Output: 1

Walk:
- inorder traversal yields [1,2,3,4]
- k=1 -> answer 1

Pitfalls to avoid

• Not stopping when k reaches 0 (extra traversal).
• Forgetting to push the left spine before popping.

Complexity

• Time: O(h + k) in best case, O(n) worst-case.
• Extra space: O(h) for the stack.

Implementation notes (Go)

• Use an explicit stack and push the left spine before popping.
• Decrement k on each pop and return when it reaches 0.