Skip to content

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

python
class Solution:
    def __init__(self):
        self.k=0
    def kthSmallest(self, R: Optional[TreeNode], k: int) -> int:
        def f(C):
            if not C:
                return -1
            l=f(C.left)
            if l!=-1:
                return l
            # left not found
            self.k+=1
            if self.k==k:
                return C.val
            return f(C.right)
        return f(R)

It can be improved to deal with node with negative values:

python
class Solution:
    def __init__(self):
        self.k=0
    def kthSmallest(self, R: Optional[TreeNode], k: int) -> int:
        def f(C):
            if not C:
                return C
            l=f(C.left)
            if l:
                return l
            # left not found
            self.k+=1
            if self.k==k:
                return C
            return f(C.right)
        return f(R).val