Problem
Kth Smallest Element in a BST
Medium- trees
- binary-search-tree
Return the k-th smallest value stored in the binary search tree root. Count from 1, so k = 1 asks for the smallest value.
Trees in this problem are written as level-order arrays: the root first, then each level from left to right. null marks a missing child, and a missing child has no entries beneath it. Trailing nulls are omitted.
- Input
root = [20, 10, 30, 5, 15, null, 40], k = 4- Output
20- Explanation
in sorted order the values are 5, 10, 15, 20, 30, 40, and the fourth of them is 20.
- Input
root = [9, 4, 12, 2, null, null, null, 1], k = 5- Output
12- Explanation
the tree has five nodes, so
k = 5asks for the largest value, 12.
Constraints:
1 <= k <= n, wherenis the number of nodes in the tree
Follow-up: if the tree changes often and you are asked for many different values of k, how would you keep each answer from costing a walk through the whole tree?
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.