You get the root of a binary search tree and an integer k. Return the value that comes k-th when every value in the tree is listed from smallest to largest, counting from 1.
In this tree, for every node, every value in its left subtree is smaller than the node's value and every value in its right subtree is larger. No two nodes hold the same value.
In increasing order the values are 1, 2, 4, 6, 9, 11. The third of them is 4.
The tree holds five values, so k = 5 asks for the largest one.
Constraints
n nodes, where 1 <= k <= n <= 10⁴.0 <= Node.val <= 10⁴An in-order walk of a binary search tree (left subtree, then the node, then the right subtree) visits the values from smallest to largest. The answer is simply the k-th node that walk reaches.
A binary search tree already keeps its values in order. You just have to read them in the right sequence.
Time O(h + k)Space O(h)
The full walkthrough and code are part of Premium
4