# CSPT25 Lecture 12
## Max Depth Binary 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
from collections import deque
class Solution:
    """
    Plan
    Recursion
    Using recursion, go through the left and right subtrees
    and keep track of the depth you're in. Once you reach a leaf
    update the maximum depth that you've found
    
    Runtime: O(n) 
    Space: O(n)
    
    Iterative
    Use a queue to keep track of the node you want to traverse
    and the depth for that node. Keep track of the highest depth found
    when processing each node
    """
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        stack = deque()
        stack.append((root, 1))
        maxDepthFound = 0
        while len(stack) > 0:
            curr = stack.pop()
            currNode, currDepth = curr[0], curr[1]
            if currDepth > maxDepthFound:
                maxDepthFound = currDepth
            if currNode.left:
                stack.append((currNode.left, currDepth + 1))
            if currNode.right:
                stack.append((currNode.right, currDepth + 1))
        return maxDepthFound
    
    def recursiveMaxDepth(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        self.maxDepthFound = 0
        self.maxDepthHelper(root, 1)
        return self.maxDepthFound
        
    def maxDepthHelper(self, currNode, currDepth):
        if currNode.left == None and currNode.right == None:
            if currDepth > self.maxDepthFound:
                self.maxDepthFound = currDepth
        if currNode.left:
            self.maxDepthHelper(currNode.left, currDepth + 1)
        if currNode.right:
            self.maxDepthHelper(currNode.right, currDepth + 1)

## Kth Smallest Element

# 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
    Go through every node in the tree and push all the values into an array as you 
    traverse it. Sort that array and get the value at index k - 1
    Runtime: O(nlogn)
    Space: O(n)
    
    Recursion
    Traverse the BST in an in-order manner, the kth node that you process is the
    node that you want
    Runtime: O(n)
    Space: O(n)
    """
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        self.numProcessed = 0
        return self.kthSmallestHelper(root, k)
        
    def kthSmallestHelper(self, currNode, k):
        if currNode.left != None:
            leftSubtree = self.kthSmallestHelper(currNode.left, k)
            if leftSubtree != None:
                return leftSubtree
        
        self.numProcessed += 1
        if self.numProcessed == k:
            return currNode.val
        
        if currNode.right != None:
            rightSubtree = self.kthSmallestHelper(currNode.right, k)
            if rightSubtree != None:
                return rightSubtree
            
        return None
    
    def bruteForceKthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = deque()
        stack.append(root)
        vals = []
        while len(stack) > 0:
            curr = stack.pop()
            vals.append(curr.val)
            if curr.left:
                stack.append(curr.left)
            if curr.right:
                stack.append(curr.right)
        vals.sort()
        return vals[k - 1]