Kth Smallest Element in a BST

medium

Given the root of a binary search tree and an integer k, return the k-th smallest value (1-indexed) of all the values of the nodes in the tree.

Test Cases

Copy an input into the main harness and Run to verify

Input

root = [3,1,4,null,2], k = 1

Expected Output

1

Input

root = [5,3,6,2,4,null,null,1], k = 3

Expected Output

3

Constraints

The number of nodes in the tree is n.
1 <= k <= n <= 10^4
0 <= Node.val <= 10^4

Hints

Hint 1 — click to reveal

An in-order traversal of a BST visits values in ascending order.

Hint 2 — click to reveal

You can stop as soon as you have seen k values — no need to finish the traversal.

Java Compiler