[Leetcode] 230. Kth Smallest Element in a BST

문제 바로가기

inorder traversal + recursive

Time Complexity: $O(n)$
Space Complexity: $O(n)$

# 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 __init__(self):
        self.i = 0
        self.res = None
        
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        def inorder(head: TreeNode):
            if head is not None and self.i < k:
                inorder(head.left)
                self.i += 1
                if self.i == k: self.res = head.val
                inorder(head.right)
                
        inorder(root)
        return self.res

inorder traversal + iterative

Time Complexity: $O(n)$
Space Complexity: $O(n)$

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if not k:
                return root.val
            root = root.right