230. Kth Smallest Element in a BST

원문: https://doljae.tistory.com/116

[Kth Smallest Element in a BST - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

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

1. In-Order Traversal using Iteration

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        answers=[]
        def inorder(cur):
            global count
            if not cur:
                return
            inorder(cur.left)
            answers.append(cur.val)
            inorder(cur.right)

        inorder(root)
        return answers[k-1]

이진 탐색 트리는 in-order로 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

2. In-Order Traversal using Stack

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        stack, count = [], 0
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            count += 1
            if count == k:
                return root.val
            root = root.right

in-order 순회는 stack으로도 구현이 가능하다.