# CSPT27 Lecture 12
## Max Depth

# 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
    The type of traversal doesn't matter. As long as we find all the leaf nodes
    and output the maximum depth found.
    Runtime: O(n)
    Space: O(n)
    """
    def maxDepth(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 currNode.left == None and currNode.right == None:
                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 maxDepthRecursive(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0
        self.maxDepthFoundSoFar = 0
        self.maxDepthHelper(root, 1)
        return self.maxDepthFoundSoFar
        
    def maxDepthHelper(self, root, currDepth):
        if root.left == None and root.right == None:
            if currDepth > self.maxDepthFoundSoFar:
                self.maxDepthFoundSoFar = currDepth
            return
        if root.left:
            self.maxDepthHelper(root.left, currDepth + 1)
        if root.right:
            self.maxDepthHelper(root.right, currDepth + 1)
        
    
    def iterativeDFSMaxDepth(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 currNode.left == None and currNode.right == None:
                if currDepth > maxDepthFoundSoFar:
                    maxDepthFoundSoFar = currDepth
            if currNode.left:
                stack.append((currNode.left, currDepth + 1))
            if currNode.right:
                stack.append((currNode.right, currDepth + 1))
        return maxDepthFoundSoFar

## 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
class Solution:
    """
    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:
            leftSubtree = self.kthSmallestHelper(currNode.left, k)
            if leftSubtree != None:
                return leftSubtree
        
        self.numProcessed += 1
        if self.numProcessed == k:
            return currNode.val
        
        if currNode.right:
            rightSubtree = self.kthSmallestHelper(currNode.right, k)
            if rightSubtree != None:
                return rightSubtree
        
        return None