# CSPT23 Lecture 12
## [Max Depth](https://leetcode.com/problems/maximum-depth-of-binary-tree/)

from collections import deque
# 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:
    """
    Plan
    Use recursion to do a depth-first traversal and return the max depth you found
    """
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        self.maxDepthFoundSoFar = 0
        self.maxDepthHelper(root, 1)
        return self.maxDepthFoundSoFar
        
    def maxDepthHelper(self, node, depth):
        if node.left == None and node.right == None and depth > self.maxDepthFoundSoFar:
            self.maxDepthFoundSoFar = depth
            return
        if node.left:
            self.maxDepthHelper(node.left, depth + 1)
        if node.right:
            self.maxDepthHelper(node.right, depth + 1)
        
    def maxDepthLevelOrder(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        queue = deque()
        queue.append((root, 1))
        maxDepthFoundSoFar = 0
        while len(queue) > 0:
            curr = queue.popleft()
            currNode, currDepth = curr[0], curr[1]
            if currDepth > maxDepthFoundSoFar:
                maxDepthFoundSoFar = currDepth
            if currNode.left:
                queue.append((currNode.left, currDepth + 1))
            if currNode.right:
                queue.append((currNode.right, currDepth + 1))
        return maxDepthFoundSoFar
    
    def maxDepthIterativeDepthFirst(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        stack = deque()
        stack.append((root, 1))
        maxDepthFoundSoFar = 0
        while len(stack) > 0:
            curr = stack.pop()
            currNode, currDepth = curr[0], curr[1]
            if currDepth > maxDepthFoundSoFar:
                maxDepthFoundSoFar = currDepth
            if currNode.right:
                stack.append((currNode.right, currDepth + 1))
            if currNode.left:
                stack.append((currNode.left, currDepth + 1))
        return maxDepthFoundSoFar

## [Kth Smallest](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)

# 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
from collections import deque
class Solution:
    """
    brute-force
    traverse the entire tree and push the values onto a list
    sort that list, return the k - 1 index
    runtime: O(nlogn)
    space: O(n)
    
    better approach
    do an inorder traversal and append values to the list, index
    correctly into the list afterwards
    runtime: O(n)
    space: O(n)
    
    best approach
    do an inorder traversal and keep track of how many nodes you've processed
    once you're processing the kth node, then you know that's the kth smallest
    value
    runtime: O(n)
    space: O(n)
    """
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.curr = 0
        return self.kthSmallestHelper(root, k)
    
    def kthSmallestHelper(self, node, k): # returns None or the kth node's value
        if node.left:
            leftSubtree = self.kthSmallestHelper(node.left, k)
            if leftSubtree != None:
                return leftSubtree
        
        self.curr += 1
        if self.curr == k:
            return node.val
        
        if node.right:
            rightSubtree = self.kthSmallestHelper(node.right, k)
            if rightSubtree != None:
                return rightSubtree
    
    def kthSmallestRecursiveNonOptimal(self, root: Optional[TreeNode], k: int) -> int:
        values = []
        self.kthSmallestHelperRecursiveNonOptimal(root, values)
        return values[k - 1]
        
    def kthSmallestHelperRecursiveNonOptimal(self, node, values):
        if node.left:
            self.kthSmallestHelper(node.left, values)
        values.append(node.val)
        if node.right:
            self.kthSmallestHelper(node.right, values)
    
    def kthSmallestBruteForce(self, root: Optional[TreeNode], k: int) -> int:
        values = []
        stack = deque()
        stack.append(root)
        while len(stack) > 0:
            curr = stack.pop()
            values.append(curr.val)
            if curr.left:
                stack.append(curr.left)
            if curr.right:
                stack.append(curr.right)
        values.sort()
        return values[k - 1]