K-th Smallest in a Search Tree

Medium

You get the root of a binary search tree: for every node, all values in its left subtree are smaller than its own value and all values in its right subtree are larger. You also get a number rank. Return the value that would stand in position rank if you listed all the tree's values in ascending order (counting from 1). As a follow-up, think about what you would do if the tree changed often and this query came in all the time.

Example 1

root=tree_node([20, 10, 30, 5, 15, None, 40]), rank=4 → 20

In ascending order the values are 5, 10, 15, 20, 30, 40. The fourth one is 20.

Example 2

root=tree_node([7, None, 9, 8]), rank=1 → 7

The root 7 is the smallest, since it has no left subtree.

Constraints

The tree has n nodes, 1 ≤ n ≤ 10⁴
1 ≤ rank ≤ n
0 ≤ Node.val ≤ 10⁴
All values are distinct and the tree is a valid search tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium Biggest Search Subtree Medium Add Every Bigger Key Medium Keep Only a Range of a Search Tree Medium

Input

root=tree_node([20, 10, 30, 5, 15, None, 40]), rank=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 43 tests on the server, hidden ones included.