K-th smallest value in a BST
You get the root of a binary search tree and a number k. In a binary search tree (BST), every value in a node's left subtree (its left child and everything below it) is smaller than the node's value and every value in its right subtree is larger, so no value appears twice.
Picture the tree's values listed from smallest to largest, and return the one in position k, counting from 1: k = 1 asks for the smallest value.
Stop as soon as you have the answer. One test asks for small values of k many times on a large tree, and visiting every node on every call is too slow there.
Trees in the examples are written in level order, the way build_tree reads them: the root, then each row from left to right, with None where a child is missing.
root = [5, 3, 7, 2, 4, None, 8], k = 3Output4From smallest to largest the values are 2, 3, 4, 5, 7, 8. The third is 4.
root = [10, 6, 15, None, 8, 12], k = 4Output12From smallest to largest: 6, 8, 10, 12, 15. The fourth is 12, the left child of 15.
root = [5, 3, 7, 2, 4, None, 8], k = 6Output8The tree has 6 nodes, so k = 6 asks for the largest value.
1 ≤ k ≤ n ≤ 2 × 105, where n is the number of nodes.
-109 ≤ node value ≤ 109, all different.
The tree is at most 500 levels deep.
The function may be called many times on the same tree.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.