Kth Smallest Element in a BST LeetCode solution in Python

1
# Runtime: 86 ms (Top 42.71%) | Memory: 18.1 MB (Top 15.27%)
2

3

4
# Definition for a binary tree node.
5
# class TreeNode:
6
# def __init__(self, val=0, left=None, right=None):
7
# self.val = val
8
# self.left = left
9
# self.right = right
10
class Solution:
11
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
12
        n = 0
13
        stack = []  # to store the elements
14
        cur = root  # pointer to iterate
15
        while cur or stack:
16
            while cur:  # used to find the left most element
17
                stack.append(cur)
18
                cur = cur.left
19
            cur = (
20
                stack.pop()
21
            )  # pop the most recent element which will be the least value at that moment
22
            n += 1
23
            if n == k:
24
                return cur.val
25
            cur = cur.right