O34
Kth Smallest Element in a BST
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) -> intInput & 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'dirExample 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:
1Example 2: k=3
Input:
[[5,3,6,2,4,null,null,1],3]Expected Output:
1Example 3: Kök
Input:
[[2,1,3],2]Expected Output:
0Example 4: Eşit Değer, Inorder İndeksi
Input:
[[2,2,3,1],2]Expected Output:
1