230. Kth Smallest Element in a BST

Description:

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

 

# 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
'''
[1] recursive)

idea::
compare the number of nodes of left sub-tree (denote it #)
if #>=k: move to left
elif #+1==k: return cur.val
else: move to right and k-=(#+1)

code::
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        
        num_left_nodes=self.getLeftCount(root.left)
        
        if num_left_nodes>=k:
            return self.kthSmallest(root.left,k)
        elif num_left_nodes+1==k:
            return root.val
        else:
            return self.kthSmallest(root.right,k-(num_left_nodes+1))
        
    def getLeftCount(self,root):
        if not root:
            return 0
        
        return self.getLeftCount(root.left)+self.getLeftCount(root.right)+1

-T/C: O(n*h)
-S/C: O(h)
'''

'''
[2] inorder)

idea::
if traverse inorder, get sorted values. so return k-1th value

code::
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        values=[]
        self.inorder(root,values)
        return values[k-1]
        
    def inorder(self,root,values):
        if not root:
            return 
        
        self.inorder(root.left,values)
        values.append(root.val)
        self.inorder(root.right,values)
        
-T/C: O(n)
-S/C: O(h)
'''
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        values=[]
        self.inorder(root,values)
        return values[k-1]
        
    def inorder(self,root,values):
        if not root:
            return 
        
        self.inorder(root.left,values)
        values.append(root.val)
        self.inorder(root.right,values)