# CSPT25 Lecture 11
## In/Post/Pre-order Traversal

# 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]:
        res = []
        if root == None:
            return res
        self.inorderTraversalHelper(root, res)
        return res
        
    def inorderTraversalHelper(self, currNode, res):
        if currNode.left:
            self.inorderTraversalHelper(currNode.left, res)
        
        res.append(currNode.val)
        
        if currNode.right:
            self.inorderTraversalHelper(currNode.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]:
        res = []
        if root == None:
            return res
        self.preorderTraversalHelper(root, res)
        return res
        
    def preorderTraversalHelper(self, currNode, res):
        res.append(currNode.val)
        
        if currNode.left:
            self.preorderTraversalHelper(currNode.left, res)
        
        if currNode.right:
            self.preorderTraversalHelper(currNode.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]:
        res = []
        if root == None:
            return res
        self.postorderTraversalHelper(root, res)
        return res
        
    def postorderTraversalHelper(self, currNode, res):
        if currNode.left:
            self.postorderTraversalHelper(currNode.left, res)
        
        if currNode.right:
            self.postorderTraversalHelper(currNode.right, res)
        
        res.append(currNode.val)

## Level-Order Traversal

# 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:
    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 = []
            nodesInNextLevel = []
            for node in nodesInLevel:
                resultForLevel.append(node.val)
                if node.left:
                    nodesInNextLevel.append(node.left)
                if node.right:
                    nodesInNextLevel.append(node.right)
            if len(nodesInNextLevel) > 0:
                queue.append(nodesInNextLevel)
            res.append(resultForLevel)
        return res

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

## Playground

from collections import deque
class BinaryTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

a = BinaryTreeNode(1)
b = BinaryTreeNode(2)
c = BinaryTreeNode(3)
d = BinaryTreeNode(4)
e = BinaryTreeNode(5)
f = BinaryTreeNode(6)
g = BinaryTreeNode(7)
h = BinaryTreeNode(8)
a.left = b
a.right = c
b.left = d
b.right = e
c.left = f
c.right = g
f.left = h

def levelOrderTraversal(root):
    res = []
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        curr = queue.popleft()
        res.append(curr.value)
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)
    return res