20_kth_smallest_element_in_bst.py

##########################################################
# Author: Raghav Sikaria
# LinkedIn: https://www.linkedin.com/in/raghavsikaria/
# Github: https://github.com/raghavsikaria
# Last Update: 20-5-2020
# Project: LeetCode May 31 Day 2020 Challenge - Day 20
##########################################################

# QUESTION
# This question is from the abovementioned challenge and can be found here on LeetCode: https://leetcode.com/explore/featured/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3335/

############################################################################
# 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?
############################################################################

# ACCEPTED SOLUTION 1
# This solution runs in O(n) Time and O(n) Space complexity

# 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.counter = 1
        self.answer = -1

    def inorder_traversal(self,root,k): 
        if root and self.answer == -1: 
            self.inorder_traversal(root.left,k)
            if self.counter == k:
                self.answer = root.val
            self.counter += 1
            self.inorder_traversal(root.right,k)
            
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.inorder_traversal(root,k)
        return self.answer

# ACCEPTED SOLUTION #2
# NEW LEARNING - APPLYING ITERATIVE
# APPROACH TO BST
# PICKED THIS UP THIS REALLY COOL SOLUTION FROM OTHER
# SUBMITTED SOLUTIONS IN THIS CHALLENGE
# DON'T KNOW THE ORIGINAL AUTHOR

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