Grokking 75: Top Coding Interview Questions
Vote

0% completed

​

Kth Smallest Element in a BST (medium)

Problem Statement

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

The values in the BST are unique.

. Examples

Example 1:

  • Input: root = [5, 3, 8, 2, 4, 7, 9, 1], k = 3
      5
     / \
    3   8
   / \  / \
  2  4 7   9
 / 
 1
  • Expected Output: 3
  • Justification: The sorted order of the elements is [1, 2, 3, 4, 5, 7, 8, 9]. The 3rd smallest value is 3.

Example 2:

  • Input: root = [6, 4, 8, 2, 5, 7, 9, 1, 3], k = 5
      6
     / \
    4   8
   /\  / \

.....

.....

.....

Like the course? Get enrolled and start learning!
C

cristiano.malossi

· 2 years ago

It assumes that the tree is ordered but this last example is not:

[10, 5, 15, 3, 7, 13, 18, 2, 4, 6, 8], k = 6

if you ask for k=8 or k=10 will not work.