Leetcode 230. Kth Smallest Element in a BST

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

We know that for a BST, left < root < right. So if we go left to the end, this is the smallest node, its root is the 2nd, and its root's right is the 3rd. In this way, we can get the kth smallest node. In order to go back, we need a stack.

Solution:

# T:O(max(h,k)) S:O(h)
class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        s, cur, rank = [], root, 0

        while s or cur:
            if cur:
                s.append(cur)
                cur = cur.left
            else:
                cur = s.pop()
                rank += 1
                if rank == k:
                    return cur.val
                cur = cur.right

        return float("-inf")

Run Time: 80 ms