Problem :

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


My Solution :

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.ans = None
self.k = k

def find(node):
if self.ans is None and node:
find(node.left)
self.k -= 1
if self.k == 0:
self.ans = node.val
return
find(node.right)

find(root)
return self.ans


Comment :

전형적인 BST Inorder Traversal 문제이다. 위는 recursion 아래는 stack 활용


My Solution2 :

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

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