1
     / \
    2   3
       / \
      4   5

    def preOrderSerializeRecursive(root: Optional[TreeNode]) -> str:
        
        def dfsPreOrder(node):
            # Note:
            # DFS pre order: root -> left -> right

            # Base case: process leaf 
            if not node:
                vals.append("N")
                return
            
            # Process root -> (DFS top down)
            vals.append(str(node.val))
            
            # Note:
            # order of recursive call determines order

            # Recursive call to process -> left -> right, left deepest 
            dfsPreOrder(node.left)
            dfsPreOrder(node.right)

            # could have been: -> right -> left
            # with deep right subtree 
            # dfsPreOrder(node.right)
            # dfsPreOrder(node.left)
        
        # serialized array
        vals = []

        # recursive call at root
        dfsPreOrder(root)

        # join serialized array
        return ",".join(vals)

    # Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: "1,2,N,N,3,4,N,N,5,N,N"

    def preOrderSerializeIterative(root: Optional[TreeNode]) -> str:
        # Note:
        # DFS pre order: root -> left -> right

        # Empty Check
        if not root:
            return "N"

        # iteration via stack
        stack = [root]

        # serialized array
        vals = []
        
        while stack:

            # dfs -> pop()
            # bfs -> popleft()
            currRoot = stack.pop()

            # process root ->: if value
            if currRoot:

                # serialize root (dfs pre order top down)
                vals.append(str(currRoot.val))
                
                # Note:
                # order of append determines order

                # Iterative process: -> left -> right
                # append(right), append(left), as pop() will pop(left), pop(right)
                # pop() leads to deep left subtree search 
                stack.append(currRoot.right)
                stack.append(currRoot.left)


                # Could have been -> right -> left
                # leading to deep right subtree search
                # stack.append(currRoot.left)
                # stack.append(currRoot.right)
            
            # process root ->: if leaf
            else:
                # serialize root (dfs pre order top down)
                vals.append("N")
        
        # join serialized array
        return ",".join(vals)

    # Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: "1,2,N,N,3,4,N,N,5,N,N"

    def bstToSortedList(root: Optional[TreeNode]) -> List[int]:
        
        # tracks previous value
        prev_val = float("-inf")
            
        def dfsInOrder(node):
            nonlocal prev_val
            
            # Base case: leaf -> no value
            if not node:
                return True
            
            # recursive call to process left subtree
            if not dfsInOrder(node.left):
                return False
            
            # process node (mid-point work)
            if node.val <= prev_val:
                return False

            # set to current value
            prev_val = node.val
            
            # recursive call to process right subtree
            return dfsInOrder(node.right)
        
        # recursive call on root
        return dfsInOrder(root)

        # Tree:
        #       2
        #      / \
        #     1   3
        # isValidBST -> True

    def isValidBST(root: Optional[TreeNode]) -> bool:
        
        # tracks previous value
        prev_val = float("-inf")

        # iteration via stack
        stack = [] 

        # pointer to check for empty case
        curr = root
        
        while stack or curr:
            
            # traverse left subtree of curr:
            # will go as far left as possible
            while curr: 
                # continue traversal down left subtree
                stack.append(curr)
                curr = curr.left
            
            # Exited loop: 
            # reached 'leaf' of left subtree
            #     L
            #  /     \ 
            # leaf    ?
                        
            # process left, node, right:
            # via previous left subtree node 'L' from stack
            curr = stack.pop()

            # validate
            if curr.val <= prev_val:
                return False

            # set to current value
            prev_val = curr.val
            
            # traverse right subtree
            # (which we thus explore left, node and right subtrees again)
            #     L
            #  /     \ 
            # leaf    *here*
            curr = curr.right
        
        return True

    # Tree:
    #       2
    #      / \
    #     1   3
    # isValidBST -> True

    def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:
        
        # global diameter
        diameter = 0

        def dfs(node):
            nonlocal diameter

            # Base case:
            # no width added
            if not node:
                return 0

            # recursive call to process left and right
            left = dfs(node.left)
            right = dfs(node.right)

            # process node
            diameter = max(diameter, left + right)

            # pass width upwards
            return 1 + max(left, right)

        # recursive on root
        dfs(root)

        # return global diameter
        return diameter

    # Tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    # diameterOfBinaryTree -> 3

    def diameterOfBinaryTree(root: Optional[TreeNode]) -> int:

        # Empty check
        if not root:
            return 0

        # global width
        diameter = 0

        # iterative stack
        stack = []

        # 
        curr = root
        lastVisited = None
        depth_map = defaultdict(int)

        while stack or curr:

            # traverse left subtree of curr:
            # will go as far left as possible
            while curr:
                stack.append(curr)
                curr = curr.left

            # check if right subtree exists
            peek = stack[-1]

            # if right subtree exists and hasn't been visited
            if peek.right and lastVisited != peek.right:
                node = peek.right

            # process node
            else:
                stack.pop()

                # grab width of left and right subtree if exists
                left_depth = depth_map.get(peek.left, 0)
                right_depth = depth_map.get(peek.right, 0)

                # node diameter
                diameter = max(diameter, left_depth + right_depth)

                # store node diameter
                depth_map[peek] = 1 + max(left_depth, right_depth)

                # set last visited to current node
                lastVisited = peek

        # return width
        return diameter

    # Tree:
    #         1
    #        / \
    #       2   3
    #      / \
    #     4   5
    # diameterOfBinaryTree -> 3 (path: 4 → 2 → 5 or 4 → 2 → 1 → 3)

    def levelOrderIterative(root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty check
        if not root:
            return []

        group = []

        # start with group 1: root
        queue = deque([root])

        while queue:

            # grab size of curr level
            size = len(queue)
            level = []

            # process entire level
            for _ in range(size):

                # grab node of group
                node = queue.popleft()
                level.append(node.val)

                # append next level
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # add level group to list of groups
            groups.append(level)

        # return all level groups
        return groups

    # Example:
    # Input Tree:
    #       1
    #      / \
    #     2   3
    #        / \
    #       4   5
    # Output: [[1], [2, 3], [4, 5]]

    def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        # start at root
        queue = deque([root])
        
        while queue:

            # grab nodes sequentially
            node = queue.popleft()
            
            # process node
            node.left, node.right = node.right, node.left
            
            # process left and right subtrees by appending to queue
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        return root

        # Example:
        # Input Tree:
        #       4
        #      / \
        #     2   7

        # Output Tree:
        #       4
        #      / \
        #     7   2

    def minDepth(root: Optional[TreeNode]) -> int:
        from collections import deque
        
        # Empty Tree
        if not root:
            return 0
        
        # initialize depth value
        queue = deque([(root, 1)])
        
        while queue:
            
            # grab current depth, increase to children
            node, depth = queue.popleft()
            
            # first leaf found -> min depth 
            if not node.left and not node.right:
                return depth
            
            # iterate to left and right subtrees with updated depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))

    def zigzagLevelOrder(root: Optional[TreeNode]) -> List[List[int]]:
        
        # Empty Tree
        if not root:
            return []
        
        groups = []

        # iteration stack
        queue = deque([root])

        # order toggle
        left_to_right = True
        
        while queue:

            # for each level
            size = len(queue)
            level = deque()
            
            # Process all nodes in current level
            for _ in range(size):
                node = queue.popleft()
                
                # append order based on pattern
                if left_to_right:
                    level.append(node.val)
                else:
                    level.appendleft(node.val)
                
                # iterate by appending left and right subtrees
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # flip order for next level
            left_to_right = not left_to_right  

            # add to groups            
            groups.append(list(level))

        return groups

    # Example:
    # Input Tree:
    #       1
    #      / \
    #     2   3
    #    / \   \
    #   4   5   6

    # Output: [[1], [3, 2], [4, 5, 6]]

    def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    
        # If both nodes smaller than root, recurse left subtree
        if p.val < root.val and q.val < root.val:
            return lowestCommonAncestor(root.left, p, q)

        # If both nodes greater than root, recurse right subtree
        elif p.val > root.val and q.val > root.val:
            return lowestCommonAncestor(root.right, p, q)
        
        # Otherwise, root is split point and LCA
        else:
            return root

    def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        curr = root

        while curr:
            # If both nodes smaller, go left
            if p.val < curr.val and q.val < curr.val:
                curr = curr.left

            # If both nodes greater, go right
            elif p.val > curr.val and q.val > curr.val:
                curr = curr.right
            
            # Else, current node is LCA
            else:
                return curr

  oh! pseudocode hasn't been written yet, try another card! :)

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # Post Order: (left -> right -> root) 
        #   1. Process left node: invert children nodes
        #   2. Process right node: invert children nodes
        #   3. Process root node: invert left and right nodes

        # Base case: reached leaf of tree, no swap, return None
        if not root:
            return None

        # Recursive call to process (left -> right) subtrees
        # could have been (right -> left) also
        leftSubtree = self.invertTree(root.left)
        rightSubtree = self.invertTree(root.right)

        # Process root: Swap left and right nodes
        root.left = rightSubtree
        root.right = leftSubtree

        # Return inverted subtree to previous root call

        # overall: tc O(n)
        # overall: sc O(h), O(log n) for balanced tree
        return root

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # BFS Iterative level by level: 
        #   1. Process Root: swap left and right
        #   2. Iterative Left And Right: children will be swapped after popped from deque
        
        # Empty Case:
        # tree is empty, no swaps needed
        if not root:
            return None
        
        # BFS Iterative Queue:
        queue = deque([root])
        

        while queue:

            # Number of nodes at depth
            size = len(queue)

            # Process all nodes in current level
            for _ in range(size):

                # Pop root node from left most of stack
                node = queue.popleft()
                
                # Process Root Node:
                # Invert left and right nodes
                node.left, node.right = node.right, node.left
                
                # Prepare Next Level:
                # Append the next level of nodes to the stack,
                # will not affect the current level processing 
                # as we have previously determined the number of nodes in the level 
                # and thus the number of nodes to be process
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return root

  oh! pseudocode hasn't been written yet, try another card! :)

    def minDepth(self, root: Optional[TreeNode]) -> int:

        # Post Order: (left -> right -> root)
        #   1. Process left node: compute its minimum depth
        #   2. Process right node: compute its minimum depth
        #   3. Process root node: combine into this node's minimum depth

        # Check:
        # reached past a leaf, empty subtree contributes no depth
        if not root:
            return 0

        # Recursive call to process (left -> right) subtrees
        leftDepth = self.minDepth(root.left)
        rightDepth = self.minDepth(root.right)

        # Check:
        # a node with only one child is NOT a leaf — minDepth must not
        # stop here, so we're forced down the side that actually exists
        if not root.left:
            return rightDepth + 1
        if not root.right:
            return leftDepth + 1

        # Check:
        # true leaf reached on both sides, or both children have subtrees —
        # take whichever side reaches a real leaf first
        subtreeMinDepth = min(leftDepth, rightDepth)

        # overall: tc O(n)
        # overall: sc O(h), O(log n) for balanced tree
        return subtreeMinDepth + 1

    def minDepth(self, root: Optional[TreeNode]) -> int:

        # BFS Iterative level by level:
        #   1. Process Root: check if it's a true leaf (no children at all)
        #   2. Iterative Left And Right: enqueue children for the next level
        #   3. Early Exit: the FIRST leaf found via BFS is guaranteed to be
        #      at the minimum depth, since BFS explores level by level —
        #      no deeper leaf could possibly be found first

        # Check:
        # tree is empty, no depth to measure
        if not root:
            return 0

        # BFS Iterative Queue: holds (node, depth) pairs
        queue = deque([(root, 1)])

        while queue:

            # Pop next node to process
            node, depth = queue.popleft()

            # Check:
            # true leaf — no left AND no right child — this is guaranteed
            # to be the minimum depth, return immediately without
            # processing the rest of the tree
            if not node.left and not node.right:
                return depth

            # Check:
            # enqueue children that exist, carrying their depth forward
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))

        # overall: tc O(n) worst case, better with early exit
        # overall: sc O(n)
        return 0

  oh! pseudocode hasn't been written yet, try another card! :)

    def maxDepth(self, root: Optional[TreeNode]) -> int:
                
        # Post Order: (left -> right -> root)
        #   Recursive into both children and pass up their depth,
        #   then process root by comparing max depth of left and right subtrees
        
        # Empty Case: 
        # tree is a leaf, no height
        if root == None:
            return 0
        
        # Recursive call to process left and right subtrees
        leftDepth = self.maxDepth(root.left)
        rightDepth = self.maxDepth(root.right)
        
        # Process Root:
        # compare max height between left and right, add 1
        rootDepth = 1 + max(leftDepth, rightDepth)

        # Return max height of subtree

        # overall: tc O(n)
        # overall: sc O(n)
        return rootDepth

    def maxDepth(self, root: Optional[TreeNode]) -> int:

        # BFS Iterative Level By Level: 
        # Process root level -> process left and right level
        #   1. Process Root: pop node from deque and do nothing
        #   2. Queue up left and right nodes to process them in the next level
        #   3. After processing all nodes in the current level, add +1 to depth counter to account for this level
        
        # Empty Case: 
        # tree is a leaf, no height
        if not root:
            return 0
        
        # BFS Iterative Queue:
        queue = deque([root])

        # Global depth
        globalDepth = 0
        
        while queue:

            # Number of nodes at current depth
            size = len(queue)

            # Process all nodes in current level
            for _ in range(size):

                # Process and do nothing
                node = queue.popleft()

                # Append the next level of nodes to the stack
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # After popping all nodes in the current level,
            # we add +1 to depth counter to account for this level in the total depth
            globalDepth += 1
        
        # overall: tc O(n)
        # overall: sc O(n)
        return globalDepth

  oh! pseudocode hasn't been written yet, try another card! :)

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        
        # DFS Pre Order: (root -> left -> right)
        # For any 2 nodes: 
        #    if both nodes are 'None' => trees match
        #    if only one node is 'None' => trees differ
        #    if values mismatch => trees differ
        #    if values match => recurse into left and right subtrees to continue validation

        # Check:
        # both nodes are leaves/None, valid match
        if not p and not q:
            return True

        # Check: 
        # only one node is 'None', invalid
        if not p or not q:
            return False

        # Check: 
        # values differ, invalid
        if p.val != q.val:
            return False
        
        # Check:
        # The two nodes match, recurse into children to continue validation,
        # if left subtree doesn't match, 'and' will skip the right subtree call, short circuit and return False early
        subTreeMatch = self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed tree
        return subTreeMatch

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        
        # BFS Iterative level by level:
        # For any 2 nodes: 
        #    if both nodes are 'None' => trees match
        #    if only one node is 'None' => trees differ
        #    if values mismatch => trees differ
        #    if values match => recurse into left and right subtrees to continue validation
        
        # BFS Iterative Queue:
        queue = deque([(p, q)])
        
        while queue:

            # Pop pair of nodes to compare
            root1, root2 = queue.popleft()
            
            # Check:
            # both nodes are leaves, valid match
            if not root1 and not root2:
                continue
            
            # Check:
            # only one node is None, invalid match
            if not root1 or not root2
                return False
            
            # Check:
            # values differ, invalid
            if root1.val != root2.val:
                return False
            
            # Check:
            # The two nodes match, recurse into children to continue validation
            queue.append((root1.left, root2.left))
            queue.append((root1.right, root2.right))
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed tree
        return True

  oh! pseudocode hasn't been written yet, try another card! :)

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

        # Symmetric Tree:
        #             1
        #          /     \
        #        2         2
        #      /   \     /   \
        #     3     4    4    3
        
        # Note: 
        # DFS Pre Order: (root -> left -> right)
        # We validate symmetry by passing the flipped node:
        #        left.left  =? right.right   (outer pair)
        #        left.right =? right.left    (inner pair)


        def isMirror(left, right):

            # Both are leaves => valid
            if left == None and right == None:
                return True

            # Only one is a leaf => invalid
            if not left or not right:
                return False

            # Values do not match => invalid
            if left.val != right.val:
                return False

            # Values match => valid

            # Validate the left and right subtrees 
            # by checking the next inner and outer pairs:
            #       - inner = left.right, right.left
            #       - outer = left.left, right.right 
            return isMirror(left.left, right.right) and isMirror(left.right, right.left)

        # Empty Check:
        # empty trees are symmetrical
        if not root:
            return True

        # Validates the root's left and right subtrees,
        # if these are mirror then tree is mirrored
        res = isMirror(root.left, root.right)

        # overall: tc O(n)
        # overall: sc O(h) unbalanced / O(log n) balanced tree
        return isMirror(root.left, root.right)

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

        # Note: 
        # BFS Iterative level by level:
        #   We validate symmetry by enqueueing the flipped node:
        #        left.left  =? right.right   (outer pair)
        #        left.right =? right.left    (inner pair)

        # Check:
        # empty tree is trivially symmetric
        if not root:
            return True

        # BFS Iterative Queue: 
        # Initialize with root's left and right subtrees
        queue = deque([(root.left, root.right)])

        while queue:

            # Pop pair of inner or outer nodes
            left, right = queue.popleft()

            # Both are leaves => valid
            if left == None and right == None:
                return True

            # Only one is a leaf => invalid
            if not left or not right:
                return False

            # Values do not match => invalid
            if left.val != right.val:
                return False

            # Values match => valid

            # Enqueue the left and right subtrees 
            # by enqueueing the next inner and outer pairs:
            #       - inner = left.right, right.left
            #       - outer = left.left, right.right 
            queue.append((left.left, right.right))
            queue.append((left.right, right.left))

        # overall: tc O(n)
        # overall: sc O(n)
        return True

  oh! pseudocode hasn't been written yet, try another card! :)

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        # Note:
        # DFS Pre Order: (root -> left -> right)
        #   Simply descend root to leaf, subtracting the nodes value from the 
        #   remaining count, and pass the remaining count as we traverse downwards.
        #   Target only counts if node has no left or right children.

        # Empty Check:
        # reached past a leaf, target not reached
        if not root:
            return False

        # Update Remaining:
        remaining = targetSum - root.val

        # Check:
        # Target found if node is a leaf and remaining is 0
        if not root.left and not root.right:
            return remaining == 0

        # Target not found, continue descent

        # overall: tc O(n)
        # overall: sc O(h) unbalanced / O(log n) balanced tree
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        # Note:
        # BFS Iterative level by level:
        #   Simply descend root to leaf, subtracting the nodes value from the 
        #   remaining count, and pass the remaining count as we traverse downwards.
        #   Target only counts if node has no left or right children.


        # Empty Check:
        # reached past a leaf, target not reached
        if not root:
            return False

        # BFS Iterative Queue: 
        # holds current node and remaining value
        queue = deque([(root, targetSum - root.val)])

        while queue:

            # Pop next node
            node, remaining = queue.popleft()

            # Check:
            # Target found if node is a leaf and remaining is 0
            if not node.left and not node.right:
                if remaining == 0:
                    return True
                continue

            # Target not found, continue descent
            # Enqueue left and right children with updated remaining
            if node.left:
                queue.append((node.left, remaining - node.left.val))
            if node.right:
                queue.append((node.right, remaining - node.right.val))

        # Queue exhausted, target not found

        # overall: tc O(n)
        # overall: sc O(h) unbalanced / O(log n) balanced tree
        return False

Sol 1: BFS Pre Order Iterative Grab Last Element Per Level
1. if not root: 
    a. return []
2. (res = [])
3. (queue = deque([root]))
4. while queue:
   a. depthLevelSize = len(queue)
   b. for i in range(depthLevelSize):
        node = queue.popleft()
        if i == depthLevelSize - 1: 
            res.append(node.val)
        if node.left: 
            queue.append(node.left)
        if node.right: 
            queue.append(node.right)
5. return res

Sol 2: DFS Modified Pre Order Root => Right => Left Add On New Depth Trigger
1. res = []
2. dfs(node, depth):
   a. if not node: 
        return
   b. if depth == len(res): 
        res.append(node.val)
   c. dfs(node.right, depth + 1)
   d. dfs(node.left, depth + 1)
3. dfs(root, 0)
4. return res

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # BFS pre order: process level : root -> left -> right
        # 1. For each level
        # 2. Process root -> :
        #    grab length of level, if root is last element in group, add to res
        # 3. Process -> left -> right :
        # Result: right most element of each level added
        
        # Empty check:
        # No rightmost to return, return empty list
        if not root:
            return []
        
        # List of the right most element for each level
        res = []
        
        # Iterative BFS queue
        queue = deque([root])
        
        while queue:

            # Number of nodes remaining in deque,
            # which represent the nodes at the current depth level
            depthLevelSize = len(queue)

            # For the number of nodes remaining in deque and this level,
            # pop and process each node in this level
            for i in range(depthLevelSize):

                # Grab the leftmost node from queue and process
                node = queue.popleft()

                # Check:
                # Validate if this node is the right most at this level
                if i == depthLevelSize - 1:
                    res.append(node.val)

                # Queue children for processing later
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # DFS Modified Pre Order: (root -> right -> left) instead of (root -> left -> right)
        # Modified pre order goes root -> right, which guarantees we explore
        # the farthest right possible, before exploring left, 
        # and with that assumption, every time we reach a new depth,
        # we are guaranteed to be at the right most element for that depth level

        # Tracking right most elements for each level
        # sc: O(n)
        res = []
        
        def dfs(node, depth):

            # Empty check:
            # Reached leaf, return
            if not node:
                return

            # Check:
            # If we have reached a new depth, using our assumption of
            # (root -> right -> left), we can guarantee that we are at the right most node
            # for this level, and can add it to our right most list 
            if depth == len(result):
                res.append(node.val)

            # Modified Pre Order:
            # Explore right subtree first, then left subtree
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        # Init depth tracker at 0
        dfs(root, 0)

        # overall: tc O(n)
        # overall: sc O(n) for skewed trees / O(log(n)) for balanced trees
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

    def goodNodes(self, root: TreeNode) -> int:

        # Note:
        # DFS Pre Order: (root -> left -> right)
        # same as max of tree, but instead of passing max upwards,
        # we pass max downwards to children to check if current node is a good node

        def dfs(node, maxSoFar):

            # Empty check:
            # no value to compare against,no good nodes
            if not node:
                return 0
            
            # Check:
            # if curr node is less than current max, not a good node, return 0
            if node.val < maxSoFar:
                good = 0
            else:
                good = 1
            
            # Update max seen so far to pass down to children
            newMax = max(maxSoFar, node.val)
            
            # Recurse into left and right subtrees, passing down the updated max
            good += dfs(node.left, newMax)
            good += dfs(node.right, newMax)
            
            # Return number of good nodes found in this subtree
            return good
        
        # Total good nodes found in tree starting from root
        totalGoodNodes = dfs(root, root.val)

        # overall: tc O(n)
        # overall: sc O(n)
        return totalGoodNodes

    def goodNodes(self, root: TreeNode) -> int:
        
        # Note:
        # DFS pre order: (root -> left -> right)
        # 1. Set maxSoFar to root and pass down to children while updating
        # 2. If node value is >= maxSoFar, it's a good node, add to count

        # global good count
        goodCount = 0

        # BFS Iterative Dequeue:
        # initialize with root as both the max value 
        # and for the node value we are comparing for a good node stack
        queue = deque([(root, root.val)])
        
        while queue:

            # Number of nodes at depth
            size = len(queue)

            # Process all nodes in current level
            for _ in range(size):

                # Pop root node and max value seen so far from left most of stack
                (root, maxSoFar) = queue.popleft()
                
                # Check:
                # if curr node is greater than the current max, its a good node
                if root.val >= maxSoFar:
                    goodCount += 1
                
                # Update max:
                newMax = max(maxSoFar, root.val)
                
                # Append children to queue with updated max value seen so far
                if root.left:
                    queue.append((root.left, newMax))
                if root.right:
                    queue.append((root.right, newMax))
        
        # overall: tc O(n)
        # overall: sc O(n)
        return goodCount

  oh! pseudocode hasn't been written yet, try another card! :)

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:

        # DFS Pre Order: (root -> left -> right)
        #   As we go from parent to children, we keep track
        #   of our coordinates and create nodes (c, r, val).
        #   Root = (row=0, col=0, root.val), and +-1 depending on left or right child,
        #   and increase for the depth.
        #   We then collect all nodes as (col, row, val) to then sort them 
        #   to account for ties during the final column grouping step

        # Nodes: collects (col, row, val) triplets for every node in the tree
        nodes = []

        def dfs(node, row, col):

            # Check:
            # node is None, nothing to record, stop descending
            if not node:
                return

            # Check:
            # record this node's coordinates and value before descending further
            nodes.append((col, row, node.val))

            # Check:
            # descend into left/right children, adjusting coordinates accordingly
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        # Sort:
        #   Take all nodes as (col, row, val) and sort them 
        #   to account for ties during the final column grouping step
        nodes.sort()

        # Check:
        # group sorted nodes by column, starting a new sublist each time
        # the column changes
        res = []

        # Tracking what column we are on,
        # iterating left to right, top to bottom, and value ascending
        prevCol = float('-inf')

        # Iterate through sorted nodes and now group them by column
        for col, row, val in nodes:

            # If we hit a new group, add new list
            if col != prevCol:
                res.append([])
                prevCol = col

            # Add node to the newest column, which because of the sort,
            # is the right most in the list 
            res[-1].append(val)

        # overall: tc O(n log n)
        # overall: sc O(n)
        return res

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:

        # BFS Iterative level by level:
        #   As we go from parent to children, we keep track
        #   of our coordinates and create nodes (c, r, val).
        #   Root = (row=0, col=0, root.val), and +-1 depending on left or right child,
        #   and increase for the depth.
        #   We then collect all nodes as (col, row, val) to then sort them 
        #   to account for ties during the final column grouping step

        # Check:
        # empty tree, nothing to traverse
        if not root:
            return []

        # Nodes: collects (col, row, val) triplets for every node in the tree
        nodes = []

        # BFS Iterative Queue: 
        # holds the tracking (node, row, col)
        queue = deque([(root, 0, 0)])

        while queue:

            # Pop next node and its coordinates
            node, row, col = queue.popleft()

            # Check:
            # record this node's coordinates and value
            nodes.append((col, row, node.val))

            # Check:
            # enqueue children with updated coordinates, only if they exist
            if node.left:
                queue.append((node.left, row + 1, col - 1))
            if node.right:
                queue.append((node.right, row + 1, col + 1))

        # Sort:
        #   Take all nodes as (col, row, val) and sort them 
        #   to account for ties during the final column grouping step
        nodes.sort()

        # Check:
        # group sorted nodes by column, starting a new sublist each time
        # the column changes
        res = []
        
        # Tracking what column we are on,
        # iterating left to right, top to bottom, and value ascending
        prevCol = float('-inf')

        # Iterate through sorted nodes and now group them by column
        for col, row, val in nodes:

            # If we hit a new group, add new list
            if col != prevCol:

                res.append([])
                prevCol = col

            # Add node to the newest column, which because of the sort,
            # is the right most in the list 
            res[-1].append(val)

        # overall: tc O(n log n)
        # overall: sc O(n)
        return res

    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:

        # DFS Pre Order: (root -> left -> right)
        # Idea:
        #    same coordinate assignment as before, but instead of a single
        #    global sort, bucket nodes by column as we go, tracking the
        #    column range so we can lay buckets out in order without
        #    sorting column keys — only sort *within* each bucket

        # cols: maps col -> list of (row, val) pairs landing in that column
        cols = defaultdict(list)
        bounds = [0, 0]  # [min_col, max_col], updated during traversal

        def dfs(node, row, col):

            # Check:
            # node is None, nothing to record, stop descending
            if not node:
                return

            # Check:
            # record this node's (row, val) under its column bucket,
            # and expand the tracked column range if needed
            cols[col].append((row, node.val))
            bounds[0] = min(bounds[0], col)
            bounds[1] = max(bounds[1], col)

            # Check:
            # descend into left/right children, adjusting coordinates accordingly
            dfs(node.left, row + 1, col - 1)
            dfs(node.right, row + 1, col + 1)

        dfs(root, 0, 0)

        # Check:
        # walk columns left to right using the tracked range (no key sort needed),
        # sorting only within each column to resolve (row, val) ties
        res = []
        for col in range(bounds[0], bounds[1] + 1):
            bucket = cols[col]
            bucket.sort()  # by row, then val
            res.append([val for row, val in bucket])

        # overall: tc O(n log n) worst case, O(n + w log b) avg — see table
        # overall: sc O(n)
        return res

  oh! pseudocode hasn't been written yet, try another card! :)

class Codec:

    # Pre Order Array + Null Markers:

    # To serialize and deserialize we need to solve these two requirements:
    #   - "where does each subtree end"
    #   - "where does the root sit"
    
    # Pre Order + Null Markers Covers Both:
    #   - Pre/post order solve "where does the root sit" for free,
    #     root is always first (pre-order) or always last (post-order),
    #     a fixed position regardless of tree shape.
    #   - Null markers solve "where does each subtree end" — an explicit
    #     sentinel marks every missing child, so the exact size of every
    #     subtree is recoverable from the token stream itself.
    #   - (So for this problem), pre-order + null markers is fully self-sufficient as we get
    #     a fixed root position through pre order and explicit subtree boundaries through Null markers

    #   - (for contrast) In order + known root solves 
    #     "everything to the left of root belongs to the left subtree and vice versa for right" 

    def serialize(self, root):

        # DFS Pre Order: (root -> left -> right)
        # Idea:
        #    walk the tree root-first, recording each node's value in visit order
        #    record a sentinel ("N") wherever a child is None, so the exact
        #    shape of the tree can be reconstructed later without ambiguity

        # vals: accumulates the pre-order token stream (values + None markers)
        vals = []

        def dfs(node):

            # Check:
            # node is None, record sentinel marker and stop descending
            if not node:
                vals.append("N")
                return

            # Check:
            # record this node's value before descending into children
            vals.append(str(node.val))

            # Check:
            # descend into left then right subtrees
            dfs(node.left)
            dfs(node.right)

        dfs(root)

        # overall: tc O(n)
        # overall: sc O(n)
        return ",".join(vals)


    def deserialize(self, data):

        # DFS Pre Order: (root -> left -> right)
        # Idea:
        #    tokens were written in pre-order, so replaying them in the same
        #    order reconstructs the same shape: pop one token per call,
        #    "N" means None, otherwise build a node and recurse for its children

        # vals: queue of tokens to consume in the exact order they were written
        vals = deque(data.split(","))

        def dfs():

            # Check:
            # next token is the None sentinel, no node here
            val = vals.popleft()
            if val == "N":
                return None

            # Check:
            # build this node before reconstructing its children,
            # mirroring the pre-order write in serialize()
            node = TreeNode(int(val))

            # Check:
            # rebuild left then right subtrees from the remaining tokens
            node.left = dfs()
            node.right = dfs()

            return node

        # overall: tc O(n)
        # overall: sc O(n)
        return dfs()

class Codec:

    # Level Order Array + Null Markers:

    # To serialize and deserialize we need to solve these two requirements:
    #   - "where does each subtree end"
    #   - "where does the root sit"

    # Level Order + Null Markers Covers Both:
    #   - Level order solves "where does the root sit" for free,
    #     root is always first — the first value dequeued/enqueued,
    #     a fixed position regardless of tree shape.
    #   - Null markers solve "where does each subtree end" — an explicit
    #     sentinel marks every missing child, so every real node's left
    #     and right slot is recorded (value or "N") in the order discovered,
    #     letting deserialize know exactly which tokens belong to which node.
    #   - (So for this problem), level-order + null markers is fully self-sufficient as we get
    #     a fixed root position through level order and explicit child boundaries through Null markers

    #   - (for contrast) In order + known root solves
    #     "everything to the left of root belongs to the left subtree and vice versa for right"

    def serialize(self, root):

        # BFS Level Order: (level by level, left -> right)
        # Idea:
        #    walk the tree level by level using a queue, recording each
        #    node's value in the order visited. Record a sentinel ("N")
        #    wherever a child is None — but unlike DFS pre-order, we do NOT
        #    enqueue past a None, since level order only ever expands
        #    children of *real* nodes. This still fully captures the shape,
        #    because every real node's left/right slot is recorded
        #    (either a value or "N") in the order it was discovered.

        # Check:
        # empty tree, single sentinel is enough
        if not root:
            return "N"

        # vals: accumulates the level-order token stream (values + None markers)
        vals = []
        queue = deque([root])

        while queue:
            node = queue.popleft()

            # Check:
            # node is None, record sentinel, don't enqueue anything for it,
            # nothing left to explore down this branch
            if not node:
                vals.append("N")
                continue

            # Check:
            # record this node's value, then queue its children
            # (queued even if None, so the None gets its own "N" slot
            # in the correct position relative to its parent)
            vals.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)

        # overall: tc O(n)
        # overall: sc O(n)
        return ",".join(vals)


    def deserialize(self, data):

        # BFS Level Order: (level by level, left -> right)
        # Idea:
        #    tokens were written level by level, so replay them the same
        #    way: pop one token per queued node to build its left child,
        #    pop the next to build its right child, enqueueing any newly
        #    built (non-None) nodes so their own children get filled in
        #    next. This mirrors the write order in serialize() exactly.

        vals = data.split(",")

        # Check:
        # single sentinel means the original tree was empty
        if vals[0] == "N":
            return None

        # root is always first (fixed position, no searching needed)
        root = TreeNode(int(vals[0]))
        queue = deque([root])
        i = 1

        while queue:
            node = queue.popleft()

            # Check:
            # next token builds node's left child, "N" means no child,
            # nothing gets enqueued for a None so we don't try to
            # expand a subtree that never existed
            if vals[i] != "N":
                node.left = TreeNode(int(vals[i]))
                queue.append(node.left)
            i += 1

            # Check:
            # next token builds node's right child, "N" means no child
            if vals[i] != "N":
                node.right = TreeNode(int(vals[i]))
                queue.append(node.right)
            i += 1

        # overall: tc O(n)
        # overall: sc O(n)
        return root

Sol 1: DFS Post Order Recursive Prune Upwards While Empty
1. children = adjacency list built from parent array
2. dfs(node):
   a. subtreeSum = value[node]
   b. remainingCount = 1
   c. for each child in children[node]:
        (childSum, childCount) = dfs(child)
        subtreeSum += childSum
        remainingCount += childCount
   d. if subtreeSum == 0:
        remainingCount = 0
   e. return (subtreeSum, remainingCount)
3. (_, remainingCount) = dfs(0)
4. return remainingCount

Sol 2: BFS Iterative Prune Upwards While Empty
1. children = adjacency list built from parent array
2. queue = deque([0])
3. order = []
4. while queue:
   a. node = queue.popleft()
   b. order.append(node)
   c. for each child in children[node]:
        queue.append(child)
5. subtreeSum = [0] * nodes
6. remainingCount = [1] * nodes
7. for each node in reversed(order):
   a. subtreeSum[node] += value[node]
   b. if subtreeSum[node] == 0:
        remainingCount[node] = 0
   c. if node != 0:
        p = parent[node]
        subtreeSum[p] += subtreeSum[node]
        remainingCount[p] += remainingCount[node]
8. return remainingCount[0]

    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        
        # Note:
        # Removing zero-sum subtrees
        # using a Parent Array (not a TreeNode with .left/.right)

        # Parent Array:
        # parent = [-1, 0, 0, 1, 2, 2, 2]
        # value  = [1, -2, 4, 0, -2, -1, -1]

        # Children Adjacency List (built from the parent array):
        # children = {
        #               0: [1, 2],
        #               1: [3],
        #               2: [4, 5, 6],
        #             }

        # Unlike TreeNode-based problems, this tree is given as a flat
        # parent array, so the first step is building a children
        # adjacency list before any top-down traversal is possible.


        # DFS Post Order Prune Upwards While Empty

        # A subtree can only be evaluated for removal once every one of
        # its own children has already been evaluated, since a node's
        # subtree sum depends on all descendants beneath it. This means
        # post-order DFS (children fully processed before the parent)
        # is the natural fit.

        # For each node, DFS returns both its subtree sum and its
        # remaining node count after any zero-sum children have already
        # collapsed to 0 nodes. If a node's own final subtree sum turns
        # out to be zero, its entire node count collapses to 0 as well,
        # which then propagates upward the same way into its parent's
        # total, since a removed subtree never contributes to
        # remainingCount above it.

        # Build Children Adjacency List:
        # tc: O(V)
        # sc: O(V)
        children = defaultdict(list)
        for i in range(1, nodes):
            children[parent[i]].append(i)

        def dfs(node):

            # Process Children First (Post Order):
            # accumulate sum and remaining count from every child
            subtreeSum = value[node]
            remainingCount = 1

            for child in children[node]:

                childSum, childCount = dfs(child)

                subtreeSum += childSum
                remainingCount += childCount

            # Prune Upwards While Empty:
            # if this subtree sums to zero, every node in it (including
            # itself) is removed, collapsing remainingCount to 0
            if subtreeSum == 0:
                remainingCount = 0

            return subtreeSum, remainingCount

        # overall: tc O(V), every node is visited exactly once in the
        #   single post-order DFS pass
        # overall: sc O(V), for the children adjacency list plus O(h)
        #   recursion stack depth, h = height of tree
        _, remainingCount = dfs(0)
        return remainingCount

    def deleteTreeNodes(self, nodes: int, parent: List[int], value: List[int]) -> int:
        
        # Note:
        # Removing zero-sum subtrees
        # using a Parent Array (not a TreeNode with .left/.right)

        # Parent Array:
        # parent = [-1, 0, 0, 1, 2, 2, 2]
        # value  = [1, -2, 4, 0, -2, -1, -1]

        # Children Adjacency List (built from the parent array):
        # children = {
        #               0: [1, 2],
        #               1: [3],
        #               2: [4, 5, 6],
        #             }

        # Unlike TreeNode-based problems, this tree is given as a flat
        # parent array, so the first step is building a children
        # adjacency list before any traversal is possible.


        # BFS Iterative Prune Upwards While Empty

        # DFS naturally processes children before parents through
        # recursion, but BFS explores top-down (root first). To
        # replicate "children before parents" iteratively, we first run
        # a standard top-down BFS just to record visitation order, then
        # process that recorded order in REVERSE, which guarantees every
        # child is processed before its parent, the same guarantee
        # post-order DFS gives us for free.

        # For each node processed in this reverse order, we accumulate
        # its subtree sum and remaining node count from its (already
        # processed) children. If a node's final subtree sum is zero,
        # its entire node count collapses to 0, which then correctly
        # propagates into its parent's total once the parent is
        # processed later in the reverse order.

        # Build Children Adjacency List:
        # tc: O(V)
        # sc: O(V)
        children = defaultdict(list)
        for i in range(1, nodes):
            children[parent[i]].append(i)

        # Iterative BFS Queue:
        # standard top-down traversal, just to record visitation order
        # sc: O(V)
        queue = deque([0])
        order = []

        while queue:

            # Pop a node from the queue
            node = queue.popleft()
            order.append(node)

            # Explore Neighbors:
            for child in children[node]:
                queue.append(child)

        # Track subtree sum and remaining node count per node
        # sc: O(V)
        subtreeSum = [0] * nodes
        remainingCount = [1] * nodes

        # Process In Reverse Order:
        # guarantees every child is fully processed before its parent
        # tc: O(V)
        for node in reversed(order):

            subtreeSum[node] += value[node]

            # Prune Upwards While Empty:
            # if this subtree sums to zero, every node in it (including
            # itself) is removed, collapsing remainingCount to 0
            if subtreeSum[node] == 0:
                remainingCount[node] = 0

            # Propagate To Parent:
            # fold this node's sum/count into its parent's running total,
            # skipped for the root, which has no parent
            if node != 0:
                p = parent[node]
                subtreeSum[p] += subtreeSum[node]
                remainingCount[p] += remainingCount[node]

        # overall: tc O(V), one BFS pass to record order, one reverse
        #   pass to compute sums/counts
        # overall: sc O(V), for the children adjacency list, order list,
        #   and the subtreeSum/remainingCount arrays
        return remainingCount[0]