The kth smallest value in a search tree

Given a binary search tree and a number k, report the kth smallest value in it. k = 1 means the smallest.

Worked example#

      5
     / \
    3   6
   / \
  2   4
 /
1

Read in order, the values are 1 2 3 4 5 6. So k = 3 gives 3.

The idea#

The whole problem is one observation: an inorder walk of a search tree visits its values in increasing order.

That falls out of the tree's own rule. At any node, everything on the left is smaller and everything on the right is larger, so "left subtree, then me, then right subtree" is exactly sorted order.

So walk inorder and count. When the count reaches k, that is the answer.

walk(node):
    walk(node.left)
    count += 1
    if count == k: answer = node.val
    walk(node.right)

Stopping early#

Collecting every value into a list and taking index k - 1 works and is a fine first version. But you can stop the moment you have counted k, and for a small k on a large tree that is the difference between touching every node and touching about k of them plus the path down to them.

Stopping needs a little care: once the answer is found, the recursion must not keep walking right subtrees on the way back up. A check at the top of the function is enough.

Why this is the BST lesson worth learning#

Almost every "kth", "range", "closest value" or "sorted order" question about a search tree is this walk with the counting changed. Once inorder-is-sorted is in your hands, those stop being separate problems.

Constraints#

• 1 <= k <= number of nodes <= 100000
• The tree really is a search tree, and values are distinct

About the input#

The tree is written level by level with null for a missing child, the count first, then k.