[leetcode]230. Kth Smallest Element in a BST

230. Kth Smallest Element in a BST

 

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

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Example 1:

Input: root = [3,1,4,null,2]

k = 1

   3

  / \

 1  4

     \

      2

Output: 1

 

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3

       5

      / \

    3   6

   / \

 2  4   

/

1 

Output: 3

 

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine

 

1. 나의 첫번째 solution 

BST 를 inorder하면 정렬된 숫자를 갖는다는 점에서 착안하여 순차적으로 data를 넣고 그중에 i 번째 원소  return

TimeComplexity = O(N)  SpaceComplextiy = O(N)

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

class Solution(object):
    def kthSmallest(self, root, k):
        li = []
        self.inorder(root, li)
        return li[k-1]
    
    def inorder(self, root, li):
        if root is None:
            return
        
        self.inorder(root.left,li)
        li.append(root.val)
        self.inorder(root.right,li)
        return
        

2번째 솔루션 : leetcode의 다른 사람 코드를 보고 배움

재귀를 없애고 반복적으로 inorder탐색을 하고 k번째에서 바로 리턴하기 

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

class Solution(object):
    def kthSmallest(self, root, k):
        stk =[]
        while True:
            while root:
                stk.append(root)
                root = root.left
            root = stk.pop()
            k -=1
            if k ==0 :
                return root.val
            root = root.right
                

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