O34

Kth Smallest Element in a BST

Mid / Senior Engineer
Target Time: 25 - 35 Minutes
Type: NUMERIC

Problem Statement & Objective

Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Function Signature (Python)

kth_smallest_bst(root: list, k: int) -> int

Input & Output Contract

Output Rule:k'ıncı inorder düğümün 0-tabanlı heap indeksi.

System Constraints

1 <= k <= düğüm sayısı <= 10^4
0 <= agac[i] <= 10^4 (null hariç)
Ağaç, yukarıdaki eşitlik kuralına uyan bir BST'dir

Example Execution Walkthrough

agac = [3, 1, 4, null, 2], k = 1
Inorder indeksleri: 1 (değer 1), 4 (değer 2), 0 (değer 3), 2 (değer 4)
k = 1 → indeks 1

agac = [2, 2, 3, 1], k = 2
        2
       / \
      2   3
     /
    1
Inorder: indeks 3 (1), indeks 1 (2), indeks 0 (2), indeks 2 (3)
k = 2 → indeks 1
Değere göre, eşitlikte küçük indeks öne alınarak sıralama k = 2 için indeks 0 verir; bu yanlıştır.

Example Test Scenarios (4)

Example 1: k=1
Input:[[3,1,4,null,2],1]
Expected Output:1
Example 2: k=3
Input:[[5,3,6,2,4,null,null,1],3]
Expected Output:1
Example 3: Kök
Input:[[2,1,3],2]
Expected Output:0
Example 4: Eşit Değer, Inorder İndeksi
Input:[[2,2,3,1],2]
Expected Output:1
Loading Python Editor...
Input Parameters
[
  [
    3,
    1,
    4,
    null,
    2
  ],
  1
]
Expected Output
1