# CSPT23 Lecture 11
## [In-order Traversal](https://leetcode.com/problems/binary-tree-inorder-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]:
        if root == None:
            return []
        res = []
        self.inorderHelper(root, res)
        return res
        
    def inorderHelper(self, node, res):
        if node.left:
            self.inorderHelper(node.left, res)
        res.append(node.val)
        if node.right:
            self.inorderHelper(node.right, res)
    
    def postorderHelper(self, node, res):
        if node.left:
            self.inorderHelper(node.left, res)
        if node.right:
            self.inorderHelper(node.right, res)
        res.append(node.val)
    
    def preorderHelper(self, node, res):
        res.append(node.val)
        if node.left:
            self.inorderHelper(node.left, res)
        if node.right:
            self.inorderHelper(node.right, res)
            
    def reversePreorderHelper(self, node, res):
        res.append(node.val)
        if node.right:
            self.inorderHelper(node.right, res)
        if node.left:
            self.inorderHelper(node.left, res)
    
    def reversePostorderHelper(self, node, res):
        if node.right:
            self.inorderHelper(node.right, res)
        if node.left:
            self.inorderHelper(node.left, res)
        res.append(node.val)
    
    def reverseInorderHelper(self, node, res):
        if node.right:
            self.inorderHelper(node.right, res)
        res.append(node.val)
        if node.left:
            self.inorderHelper(node.left, res)

## [Level Order Traversal](https://leetcode.com/problems/binary-tree-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()
            nextLevel = []
            resultForLevel = []
            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

## [isValidBST](https://leetcode.com/problems/validate-binary-search-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:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True
        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

## Sandbox

from collections import deque

class BinaryTreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

a = BinaryTreeNode(1)
b = BinaryTreeNode(2)
c = BinaryTreeNode(3)
d = BinaryTreeNode(4)
e = BinaryTreeNode(6)

a.left = b
a.right = c
b.left = d
c.left = e

def levelOrderTraversal(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        curr = queue.popleft()
        print(curr.val)
        if curr.left:
            queue.append(curr.left)
        if curr.right:
            queue.append(curr.right)

def reverseLevelOrderTraversal(root):
    queue = deque()
    queue.append(root)
    while len(queue) > 0:
        curr = queue.popleft()
        print(curr.val)
        if curr.right:
            queue.append(curr.right)
        if curr.left:
            queue.append(curr.left)

levelOrderTraversal(a)