# CSPT 19 Lecture 9
## Traversals

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.postorderTraversalHelper(root, res)
        return res
        
        
    def postorderTraversalHelper(self, currNode, res):
        if currNode == None:
            return
        
        if currNode.left != None:
            self.postorderTraversalHelper(currNode.left, res)
        
        if currNode.right != None:
            self.postorderTraversalHelper(currNode.right, res)
        
        res.append(currNode.val)

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.inorderTraversalHelper(root, res)
        return res
        
        
    def inorderTraversalHelper(self, currNode, res):
        if currNode == None:
            return
        
        if currNode.left != None:
            self.inorderTraversalHelper(currNode.left, res)
            
        res.append(currNode.val)
        
        if currNode.right != None:
            self.inorderTraversalHelper(currNode.right, res)
        
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.inorderTraversalHelper(root, res)
        return res
        
        
    def inorderTraversalHelper(self, currNode, res):
        if currNode == None:
            return
        
        if currNode.left != None:
            self.inorderTraversalHelper(currNode.left, res)
            
        res.append(currNode.val)
        
        if currNode.right != None:
            self.inorderTraversalHelper(currNode.right, res)
class Solution:
    def levelOrder(self, root: 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 != None:
                    nextLevel.append(node.left)
                if node.right != None:
                    nextLevel.append(node.right)
            if len(nextLevel) > 0:
                queue.append(nextLevel)
            res.append(resultForLevel)
        return res

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

class Solution:
    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, currMin, currNode.val))
            if currNode.right != None:
                stack.append((currNode.right, currNode.val, currMax))
        return True