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

from collections import deque
class Solution:
    """
    Plan
    Traverse the entire tree, while keeping track of the
    depth found for each node. Return the max depth found.
    Runtime: O(n)
    Space: O(n)
    """
    def maxDepth(self, root: TreeNode) -> int:
        if root == None:
            return 0
        self.maxDepth = 0
        self.maxDepthHelper(root, 1)
        return self.maxDepth
    
    def maxDepthHelper(self, root, currDepth):
        # base-case
        if root.left == None and root.right == None:
            if currDepth > self.maxDepth:
                self.maxDepth = currDepth
            return
        # recursive-cases
        if root.left != None:
            self.maxDepthHelper(root.left, currDepth + 1)
        if root.right != None:
            self.maxDepthHelper(root.right, currDepth + 1)
    
    def iterativeMaxDepth(root):
        if root == None:
            return 0
        queue = deque()
        queue.append((root, 1))
        maxDepthFound = 1
        while len(queue) > 0:
            curr = queue.popleft()
            currNode, currDepth = curr[0], curr[1]
            if currDepth > maxDepthFound:
                maxDepthFound = currDepth
            if currNode.left != None:
                queue.append((currNode.left, currDepth + 1))
            if currNode.right != None:
                queue.append((currNode.right, currDepth + 1))
        return maxDepthFound

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

class Solution:
    """
    Plan
    1. Traverse in an in-order traversal manner. Keep track
    of the number of node you visited. If k == numNodeVisited
    then return node.value
    2. Traverse in an in-order manner. Push node's value into a list
    when it's time to process that node. In the end, you have a list of
    sorted values. Just index correctly to get the kth node's value
    """
#     def kthSmallest(self, root: TreeNode, k: int) -> int:
#         res = []
#         self.kthSmallestHelper(root, k, res)
#         return res[k - 1]
    
#     # Return the kth node's value OR None
#     def kthSmallestHelper(self, root, k, res):
#         # recursive-case 1
#         if root.left != None:
#             self.kthSmallestHelper(root.left, k, res)
        
#         res.append(root.val)
        
#         # recursive case 2
#         if root.right != None:
#             self.kthSmallestHelper(root.right, k, res)
    
    
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.curr = 0
        return self.kthSmallestHelper(root, k)
    
    # Return the kth node's value OR None
    def kthSmallestHelper(self, root, k):
        # recursive-case 1
        if root.left != None:
            leftSubtree = self.kthSmallestHelper(root.left, k)
            if leftSubtree != None:
                return leftSubtree
        
        self.curr += 1
        # base-case
        if self.curr == k:
            return root.val
        
        # recursive case 2
        if root.right != None:
            rightSubtree = self.kthSmallestHelper(root.right, k)
            if rightSubtree != None:
                return rightSubtree
        
        return None

## [Construct Tree]()

"""
Understand

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

    3
    / \
    9  20
    /  \
    15   7

Plan
Realize that the left part of the inorder array of a given node is its left subtree
The right part of the inorder array is its right subtree
Therefore, we can recreate the tree by going through each node in the preorder list and finding its index
in the inorder list. We create that node and to recreate its subtrees, we recurse.

Runtime: O(number of nodes)
Space: O(number of nodes)
"""
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
    return self.buildTreeHelper(deque(preorder), inorder, 0, len(inorder) - 1)

def buildTreeHelper(self, preorder, inorder, inorderStartIndex, inorderEndIndex):
    if len(preorder) == 0 or inorderStartIndex > inorderEndIndex or inorderStartIndex < 0 or inorderEndIndex >= len(inorder):
        return None

    value = preorder.popleft()
    node = TreeNode(value)
    inorderIndex = inorder.index(value)

    node.left = self.buildTreeHelper(preorder, inorder, inorderStartIndex, inorderIndex - 1)
    node.right = self.buildTreeHelper(preorder, inorder, inorderIndex + 1, inorderEndIndex)
    return node