Binary Search Trees Using the ordering
388. Kth Smallest Element in a BST
You are given root, the root node of a binary search tree, and an integer k. Return the k-th smallest
value in the tree. k counts from 1, so k = 1 asks for the smallest value.
In a binary search tree, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger. The values in the tree are distinct.
The examples write a tree level by level, from left to right, with null where a child is missing. So
root = [5,8,null,3] is the root 5 with a left child 8 and no right child, and 8 has a left child 3. The
missing children after the last node are left out.
Example 1
Input: root = [20, 8, 30, 4, 12, 25, 40, null, null, 10, 14]
k = 4
12Explanation: From smallest to largest, the values are 4, 8, 10, 12, 14, 20, 25, 30, 40. The fourth of them is 12.
Example 2
Input: root = [0, -1000000000, 1000000000, null, -500]
k = 3
0Explanation: From smallest to largest, the values are −109, −500, 0, 109. The third is the root, 0.
Example 3
Input: root = [6, 2, null, null, 4, 3, 5], k = 5
6Explanation: The tree has 5 nodes, so k = 5 asks for the largest value. That is 6, at the root.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 109- The tree has at most 1000 levels.
- The tree is a binary search tree, and its values are distinct.
1 ≤ k ≤ number of nodes
Clarifying questions
What you would ask an interviewer before writing any code.