Problem Statement

Kth Smallest Element in a BST

You are given the top node, called the root, of a binary search tree. A binary search tree, or BST, is a tree where every node has at most two children, and there is a rule about where values go: everything to the left of a node is smaller than it, and everything to the right is larger. You are also given a number k. Your job is to return the kth smallest value in the tree, counting from 1. So k equals 1 means the very smallest value, k equals 2 means the second smallest, and so on.

mediumTreeTreesTime: O(H + k) · Space: O(H)

Signals to notice

find kth smallest in BSTin-order traversal gives sorted orderearly termination

Brute force first

Collect all elements via in-order traversal, return the kth. Visits every node even if k is 1. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

In-order traversal with a counter: visit left, decrement k, if k = 0 return current value, else visit right. Stops as soon as the kth element is found. on average. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `root = [5,3,6,2,4,null,null,1], k = 3`

Start: stack=[], node=5, count=0. Tree in-order = 1,2,3,4,5,6.
Inner dive from 5: push 5,3,2,1 -> stack=[5,3,2,1], node=null (leftmost reached).
Pop 1: count=1, 1!=k. node=1.right=null.
Pop 2: count=2, 2!=k. node=2.right=null.
Pop 3: count=3 == k -> return 3.

What must stay true

In-order traversal of a BST visits nodes in ascending order. The kth node visited is the kth smallest. Counting lets you stop early without visiting all n nodes. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

stack = []; node = root; count = 0
while stack or node:
    while node: stack.push(node); node = node.left   # dive to leftmost
    node = stack.pop(); count += 1                    # visit in ascending order
    if count == k: return node.val                    # stop early
    node = node.right                                 # explore right subtree

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not stopping early — in-order traversal visits all nodes if you don't break when k reaches 0. Use iterative traversal with a stack for easy early termination. Most mistakes here are not about syntax; they come from losing track of what your state, pointer, or structure is supposed to mean.

Trees Pattern