Problem statement

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

Solution

Just do inorder traversal with stack (see problem 0094). Then we have complexity O(h + k), where h is the height of tree. If we want to do it a lot of times, we can keep number of all children for each node, which is O(n) memory, then we can have $O(h)$ complexity to find k-th element, using something like binary search.

Complexity

Time complexity is O(h + k), space complexity is O(h).

Code

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