# CSPT27 Lecture 11
## Depth-first Traversals

# 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:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        self.inorderTraversalHelper(root, res)
        return res
        
    def inorderTraversalHelper(self, currentNode, res):
        if currentNode.left:
            self.inorderTraversalHelper(currentNode.left, res)
        
        res.append(currentNode.val)
        
        if currentNode.right:
            self.inorderTraversalHelper(currentNode.right, res)

# 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:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        self.preorderTraversalHelper(root, res)
        return res
        
    def preorderTraversalHelper(self, currentNode, res):
        res.append(currentNode.val)
        
        if currentNode.left:
            self.preorderTraversalHelper(currentNode.left, res)
        
        if currentNode.right:
            self.preorderTraversalHelper(currentNode.right, res)

# 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:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        self.postorderTraversalHelper(root, res)
        return res
        
    def postorderTraversalHelper(self, currentNode, res):
        if currentNode.left:
            self.postorderTraversalHelper(currentNode.left, res)
        
        if currentNode.right:
            self.postorderTraversalHelper(currentNode.right, res)
            
        res.append(currentNode.val)

## Level Order Traversal

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:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root == None:
            return []
        res = []
        queue = deque()
        queue.append([root])
        while len(queue) > 0:
            nodesInLevel = queue.popleft()
            resultForLevel = []
            nextLevel = []
            for node in nodesInLevel:
                resultForLevel.append(node.val)
                if node.left:
                    nextLevel.append(node.left)
                if node.right:
                    nextLevel.append(node.right)
            if len(nextLevel) > 0:
                queue.append(nextLevel)
            res.append(resultForLevel)
        return res

## Validate BST

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:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        stack = deque()
        stack.append((root, float("-inf"), float("inf")))
        while len(stack) > 0:
            curr = stack.pop()
            currNode, currMin, currMax = curr[0], curr[1], curr[2]
            if currNode.val <= currMin or currNode.val >= currMax:
                return False
            if currNode.left:
                stack.append((currNode.left, currMin, currNode.val))
            if currNode.right:
                stack.append((currNode.right, currNode.val, currMax))
        return True