Kth Smallest Element in a BST

Medium

Trees Recursion DFS (Depth-First Search)Binary Tree Traversal

Problem

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.

Constraints

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

Examples

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

Output: 1

The inorder traversal of the tree is [1, 2, 3, 4]. The 1st smallest element is 1.

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

Output: 3

The inorder traversal is [1, 2, 3, 4, 5, 6]. The 3rd smallest element is 3.

Loading...

Loading Python...