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

    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

    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

    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

    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

    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

    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

    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

    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

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

    def recoverTree(self, root: Optional[TreeNode]) -> None:

        # Note: 
        # DFS In Order: (left -> root -> right)
        #   Traversing a valid BST results in strictly ascending values.
        #   If 2 nodes were swapped, the sequence will contain 1 or 2 violations,
        #   a value smaller than the one right before it.
        #   Track 'prev' as we go to detect violations without ever storing the full
        #   sequence in a list.
        #   'First' will be set to the first violation previous node.
        #   'Second' will be set on the second violation.

        self.first = None
        self.second = None
        self.prev = None

        def dfs(node):

            # Empty Check:
            # no values, return
            if not node:
                return

            # In Order Traversal:
            # will result in strictly ascending, except for the violation
            dfs(node.left)

            # Check:
            # The violation will cause the current value to be smaller than the previous
            if self.prev and self.prev.val > node.val:

                # First violation found: 
                # Prev is standing at node before first violation,
                # set first to prev.
                # first swapped node
                if self.first == None:
                    self.first = self.prev

                # Second will be set for the first and second violation,
                # ending up correct after the second violation:
                self.second = node

            # Check:
            # advance prev before continuing traversal
            self.prev = node

            # Check:
            # descend right last, completing the in-order sequence
            dfs(node.right)

        dfs(root)

        # Check:
        # swap the VALUES (not the nodes themselves) to restore BST order
        # without altering the tree's structure
        self.first.val, self.second.val = self.second.val, self.first.val

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

    def recoverTree(self, root: Optional[TreeNode]) -> None:

        # Note:
        # Morris In Order Traversal: (left -> root -> right), O(1) space
        #   Traversing a valid BST results in strictly ascending values.
        #   If 2 nodes were swapped, the sequence will contain 1 or 2 violations,
        #   a value smaller than the one right before it.
        #   We avoid a recursion stack or an explicit stack by temporarily
        #   threading the tree using Morris Traversal by using unused right pointers


        first = second = prev = None
        node = root

        while node:

            # No Left Subtree:
            # safe to process this node directly, move right nothing left to thread
            if not node.left:

                # Check:
                # same violation detection as Solution 1
                if prev and prev.val > node.val:
                    if first == None:
                        first = prev
                    # Second will be set for the first and second violation,
                    # ending up correct after the second violation:
                    second = node

                prev = node
                node = node.right

            # Left Subtree:
            else:

                # In Order Iteration Results In Ascending:
                # grab left and the rightmost node in left's subtree 
                predecessor = node.left
                while predecessor.right and predecessor.right != node:
                    predecessor = predecessor.right

                # Traversed the left's right subtree and found the rightmost unused right point,
                # will use this to thread back to node
                if predecessor.right == None:
                    # thread, and iterate to left subtree
                    predecessor.right = node
                    node = node.left

                # Thread already exists, 
                # we've returned here after finishing the left subtree, 
                # remove the thread to restore the tree, process `node`, then move right
                else:

                    # Revert temp right point thread to None
                    predecessor.right = None

                    # 
                    if prev and prev.val > node.val:

                        # First and second violation
                        if first == None:
                            first = prev

                        # Second will be set for the first and second violation,
                        # ending up correct after the second violation:
                        second = node

                    # Continue iteration
                    prev = node
                    node = node.right

        # Swap the violations values and restore the tree
        first.val, second.val = second.val, first.val

        # overall: tc O(n)
        # overall: sc O(1)