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

kth_smallest_in_bst.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        '''

        we can imagine some logN process, which we need to call K times, giving us KlogN time complexity.
        or maybe even O(1) process * K, but that sounds like asking for too much. 

        with in-order traversal, worst case is O(N), best case is O(logN)
        0 ms, beats 100% with early-stop mechanism.
        
        the space complexity is probably around O(k + logn), since you need to traverse on average logn nodes to get to the leftmost value with in-order traversal, 
        and then you need to go through an additional k-1 more nodes on average. 
        The reason why it's important to account for this aspect of space complexity is because this solution can be performed via a stack (type of DFS). 
        So the stack in that solution should count as space complexity just as much as a recursive solution.

        how to optimise for frequent modifications to the BST:
            - turn it into a heap? maybe that's too much wasted compute. each heappop is O(logN) so time complexity is O(KlogN). for each insert, it can be done in O(logN) time. but deleting arbitrary nodes is trickier...
            - if K is fixed, then first find the original Kth smallest node, and just keep track of which nodes got deleted or inserted and whether they're above or below the original kth smallest value? hmm
            - if K is variable, then it's trickier...
        '''
        self.cnt = 0
        self.res = None

        # in order traversal
        def visit(node: Optional[TreeNode]):
            if self.res is not None:
                # found already, early stop
                return
            if node is None:
                return

            visit(node.left)
            # using just `cnt` didnt work, strange...
            self.cnt += 1
            if self.cnt == k:
                self.res = node.val
                return
            visit(node.right)
            return

        visit(root)
        return self.res

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/
in order traversal without recursion but using stack, so O(N) memory cost regardless just without recursion stack

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
O(1) memory using Morris Traversal