Problem statement

https://binarysearch.com/problems/Kth-Smallest-in-a-Binary-Search-Tree/

Solution

Equal to Leetcode 0230. Kth Smallest Element in a BST

Complexity

It is O(k) for time and space.

Code

class Solution:
    def solve(self, root, k):
        stack, curr = [], root
        
        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            
            if k == 0:
                return curr.val
            
            k -= 1
            curr = curr.right