230. Kth Smallest Element in a BST - python3

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

My Answer 1: Accepted (Runtime: 52 ms - 55.11% / Memory Usage: 17.9 MB - 54.93%)

# 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: TreeNode, k: int) -> int:
        queue = [root]
        result = []
        while queue:
            root = queue.pop(0)
            if root is not None:
                result.append(root.val)
                if root.left:
                    queue.append(root.left)
                if root.right:
                    queue.append(root.right)
        result = sorted(result)
        return result[k-1]

오늘도 멋진 비효율 코드부터 생각났다^^

트리를 순회하면서 리스트 값으로 저장하고 sorted 로 정렬 후 k-1 인덱스의 값을 반환
순회는 안써본 level-order traversal 을 사용

주어진 BST 의 특징을 생각 안하고 그냥 무작정 덤빔

[Python] 트리 순회 알고리즘 참고: https://gingerkang.tistory.com/87

My Answer 2: Accepted (Runtime: 52 ms - 55.11% / Memory Usage: 18.2 MB - 7.89%)

# 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: TreeNode, k: int) -> int:
        result = []
        
        def _in_order_traversal(root):
            if root is None:
                pass
            else:
                _in_order_traversal(root.left)
                result.append(root.val)
                _in_order_traversal(root.right)
            
        _in_order_traversal(root)
        return result[k-1]

in-order traversal 을 이용하면 정렬 필요없이 할 수 있다

Solution 1: Accepted (Runtime: 52 ms - 55.11% / Memory Usage: 18.2 MB - 13.47%)

# 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: TreeNode, k: int) -> int:
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
    
        return inorder(root)[k - 1]

in-order 를 사용하는게 핵심인듯

Recursive Inorder Traversal
It's a very straightforward approach with \mathcal{O}(N)O(N) time complexity. The idea is to build an inorder traversal of BST which is an array sorted in the ascending order. Now the answer is the k - 1th element of this array.