Kth Smallest Element in a BST
Given the root of a binary search tree and an integer k, return the k-th smallest value among all the node values. Counting starts at 1, so k = 1 asks for the minimum.
The tree contains at least k nodes. Return a number.
Constraints
- The tree has
nnodes, with1 <= k <= n <= 10^4. 0 <= Node.val <= 10^4(the tests also use negative values).- All values are distinct.
Examples
Example 1
Input: root = [3,1,4,null,2], k = 1 Output: 1
In sorted order the values are 1, 2, 3, 4. The 1st smallest is 1.
Example 2
Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3
Sorted order is 1, 2, 3, 4, 5, 6. The 3rd smallest is 3.
Example 3
Input: root = [5,3,6,2,4,null,null,1], k = 6 Output: 6
k may equal the number of nodes: the 6th smallest is the maximum.
JavaScript you'll use: Recursion, the call stack and memoization Linked list and tree nodes
/**
* Tree nodes are provided (you don't need to define them):
* class TreeNode { constructor(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; } }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
function kthSmallest(root, k) {
}
Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.