Kth Smallest Element in a BSTMedium

Kth Smallest Element in a BST

Medium 9.6k71% acceptance

TreeDepth-First SearchBinary Search TreeBinary Tree

Given the root of a binary search tree and an integer k, return the value of the k-th smallest element in the tree.

k is 1-indexed, so k = 1 asks for the minimum value. You may assume 1 ≤ k ≤ the number of nodes.

The tree is given in level-order (TreeNode with { val, left, right }, null for a missing child).

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 values are 1, 2, 3, 4, 5, 6; the 3rd smallest is 3.

Example 3

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

Output: 2

Constraints

Asked atAmazonGoogleMicrosoftUber

JavaScript

⌘↵ to run

Loading editor…

Case 1

[3,1,4,null,2], 1

expected: 1

Case 2

[5,3,6,2,4,null,null,1], 3

expected: 3

Case 3

[2,1,3], 2

expected: 2

Case 4

[1], 1

expected: 1

Case 5

[3,1,4,null,2], 4

expected: 4

Case 6

[5,3,6,2,4,null,null,1], 6

expected: 6