Confused? Click this! Unlock the secrets of BSTs!
Intuition\n Describe your first thoughts on how to solve this problem. \nThe property of BST allows us to traverse it from smallest node to largest simply with 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe property of BST allows us to traverse it from smallest node to largest simply with an **in-order DFS**.\n\nWhat is the smallest node in a BST? It\'s the leftmost node. What\'s the second smallest? It\'s the leftmost node\'s parent, p. What\'s the third smallest? It\'s p\'s right child, or the leftmost node\'s sibling.\n\nThus we can infer that an in-order DFS traversal, left -> current -> right, will traverse from smallest to largest.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe traverse the tree with **in-order DFS**, meaning left -> current -> right. We can do this recursively or iteratively, but this case we do it recursively.\n\nWe increment i by 1 whenever we visit a node (we can also decrement k by 1 and check k == 0). If our current node results in i == k, we know it\'s the kth smallest node and set res to current node\'s value.\n\nReturn res.\n# Complexity\n- Time complexity: **O(n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(logn)** if tree is balanced, **O(n)** if tree is skewed\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\nclass Solution:\n\n    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n        stack, cur = [], root # first in, last out\n        \n        # iterative in-order DFS traversal\n        while True:\n            while cur: # go as left as possible\n                stack.append(cur)\n                cur = cur.left\n\n            cur = stack.pop() # last one, smallest node\n            k -= 1\n            if k == 0:\n                return cur.val\n                \n            cur = cur.right\n\n\n```
['Python3']