# CSPT17 Lecture 9
## Depth-first Traversals

"""
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/binary-tree-preorder-traversal/
https://leetcode.com/problems/binary-tree-postorder-traversal/
https://leetcode.com/problems/binary-tree-level-order-traversal/
"""

# Post-order
def postorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    if root != None:
        self.postorderTraversalHelper(root, res)
    return res

def postorderTraversalHelper(self, root, res):
    if root == None:
        return

    # go to left subtree first
    if root.left != None:
        self.postorderTraversalHelper(root.left, res)

    # go to right subtree next
    if root.right != None:
        self.postorderTraversalHelper(root.right, res)

    # process current node
    res.append(root.val)

# Pre-order 
def preorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    if root != None:
        self.preorderTraversalHelper(root, res)
    return res

def preorderTraversalHelper(self, root, res):
    if root == None:
        return

    # process current node
    res.append(root.val)

    # go to left subtree first
    if root.left != None:
        self.preorderTraversalHelper(root.left, res)

    # go to right subtree next
    if root.right != None:
        self.preorderTraversalHelper(root.right, res)

# In-order
def inorderTraversal(self, root: TreeNode) -> List[int]:
    res = []
    if root != None:
        self.inorderTraversalHelper(root, res)
    return res

def inorderTraversalHelper(self, root, res):
    if root == None:
        return
    # go to left subtree first
    if root.left != None:
        self.inorderTraversalHelper(root.left, res)
    # process current node
    res.append(root.val)
    # go to right subtree next
    if root.right != None:
        self.inorderTraversalHelper(root.right, res)

## [Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    self.res = []
    if root != None:
        self.levelOrderHelper(root)
    return self.res

def levelOrderHelper(self, root):
    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 != None:
                nextLevel.append(node.left)
            if node.right != None:
                nextLevel.append(node.right)
        if len(nextLevel) > 0:
            queue.append(nextLevel)
        self.res.append(resultForLevel)

## [Valid BST](https://leetcode.com/problems/validate-binary-search-tree/)

def isValidBST(self, root: 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 != None:
            stack.append((currNode.left, min(currNode.left.val, currMin), currNode.val))
        if currNode.right != None:
            stack.append((currNode.right, currNode.val, max(currNode.right.val, currMax)))
    return True