Kth Smallest Element In a Bst

Medium · Trees

You are given the root of a binary search tree and a positive integer k. Treat all the node values as if they were laid out in ascending order and return the value that would sit in position k of that ordering, counting from 1. The tree respects the usual BST rule where every left descendant is smaller and every right descendant is larger than its ancestor.

Examples

Input:  root = [3,1,4,null,2], k = 1
Output: 1
Why:    Sorted order of values is 1,2,3,4 so the 1st smallest is 1.

Input:  root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Why:    Sorted order of values is 1,2,3,4,5,6 so the 3rd smallest is 3.

Input:  root = [1,null,2], k = 2
Output: 2
Why:    Sorted order of values is 1,2 so the 2nd smallest is 2.

Constraints

1 <= number of nodes <= 10^4, 0 <= Node.val <= 10^4, 1 <= k <= number of nodes

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Kth Smallest Element In a Bst

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Kth Smallest Element In a Bst. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.