def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Inorder Traversal: (left -> root -> right)
        # Recursion stack will serve as queue to explore the most recent node
        #   - In order requires to explore left first, recurse as far left as possible
        #   - Finished exploring left, 'Visit' node
        #   - Step into right node
        #   - Repeat
        
        res = []
        
        def dfs(node):

            # Base case: 
            # reached a leaf's child 'None'
            if not node:
                return
            
            # In order requires to explore left first, 
            # so push as many left nodes to stack for this root
            dfs(node.left)

            # Recurse until exhausted
            
            # Finished exploring left, 'Visit' node
            res.append(node.val)
            
            # Step into right node
            dfs(node.right)

            # Repeat
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return res

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Inorder Traversal: (left -> root -> right) using a Stack
        # Stack will serve as queue to explore the most recent node
        #   - In order requires to explore left first, so push as many left nodes to stack for this root
        #   - Finished exploring left, 'Visit' node
        #   - Step into right node
        #   - Repeat
        
        # Initial Helper Root Node
        # We need a helper root node unlike the other 2 iterative solutions
        # because Inorder requires us to go left first,
        # which requires a node, but since we can't push anything
        # to the stack without modifying the Inorder order,
        # we need a helper
        # sc: O(1)
        node = root
        
        res = []

        # Iterative Node Stack
        # sc: O(n)
        stack = []

        # Traverse until
        #   - curr node is a a leaf child 'None'
        #   - there are no nodes in stack queue to traverse
        while node or stack:
            
            # In order requires to explore left first, 
            # so push as many left nodes to stack for this root
            while node:
                stack.append(node)
                node = node.left
            
            # Reached a 'None' child leaf, 
            # we've reached as far left as we can go

            # Pop the leftmost node at top of queue
            node = stack.pop()
            
            # 'Visit' node
            res.append(node.val)
            
            # Step into right node
            node = node.right

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

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Recursive Preorder Traversal: (root -> left -> right)
        # Recursion stack will serve as queue to explore the most recent node
        #   - In order requires to explore root first, 'Visit' node
        #   - Recurse into left node
        #   - start over
        #   - Run out of left nodes, recurse to right node
        #   - start over
        
        res = []
        
        def dfs(node: Optional[TreeNode]):
            
            # Base case: 
            # reached a leaf's child 'None'
            if not node:
                return
            
            # In order requires to explore root first, 'Visit' node
            res.append(node.val)
            
            # Recurse into left node
            dfs(node.left)

            # Recurse until exhausted
            
            # Finished exploring left, now explore right
            dfs(node.right)

            # Repeat
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return res

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Iterative Preorder Traversal: (root -> left -> right) using a Stack
        # Stack will serve as queue to explore the most recent node
        #   - In order requires to explore left first, so push as many left nodes to stack
        #   - Pop from stack, 'Visit' node
        #   -
        #   - Pop node from stack, visit it
        #   - Push right child first, then left child so left is processed first
        
        # Early Exit:
        # tree is empty, return empty array
        if not root:
            return []
        
        res = []

        # Iterative Node Stack
        # sc: O(n)
        stack = [root]
        
        # Traverse until
        #   - There are no nodes in stack queue to traverse
        while stack:

            # In order requires to explore root first, 'Visit' node
            node = stack.pop()            
            res.append(node.val)
            
            # Queue RIGHT before LEFT so LEFT is popped first (LIFO)

            # Eventually, we will repeat on right
            if node.right:
                stack.append(node.right)

            # Eventually, we will iterate until exhausted
            if node.left:
                stack.append(node.left)
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return res

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        # Postorder Traversal: (left -> right -> root)
        # Recursion stack will serve as queue to explore the most recent node
        #   - Post order requires to explore left first, recurse as far left as possible
        #   - Go up recursive calls, visit node
        #   - start over
        #   - Run out of left nodes, recurse to the right node
        #   - start over
        #   - Run out of right nodes, 'Visit' root node
        #   - start over
        
        res = []
        
        def dfs(node: Optional[TreeNode]):

            # Base case: 
            # reached a leaf's child 'None'
            if not node:
                return
            
            # In order requires to explore left first, 
            # so push as many left nodes to stack for this root
            dfs(node.left)
            
            # Finished exploring left, now explore right
            dfs(node.right)
            
            # 'Visit' node
            res.append(node.val)
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return res

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        # Post Traversal: (left -> right -> root) using a Stack
        # Stack will serve as queue to explore the most recent node
        #   - Post order requires to explore left first, so push as many left nodes to stack for this root
        #   - Use a modified preorder: root -> right -> left
        #   - Reverse the result at the end to get correct postorder
        
        # Early Exit:
        # tree is empty, return empty array
        if not root:
            return []
        
        res = []
        
        # Iterative Node Stack
        # sc: O(n)
        stack = [root]
        
        # Traverse until
        #   - There are no nodes in stack queue to traverse
        while stack:

            # 'Visit' node
            node = stack.pop()
            res.append(node.val)
            
            # Postorder: push LEFT first so RIGHT is processed first (LIFO)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        # Puts this on stack:       root -> right -> left
        # When popped off stack is: left -> right -> root
        res.reverse()
        
        # overall: tc O(n)
        # overall: sc O(h + n), O(h) for stack, O(n) for result array
        return res

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        # Tree Widths:
        # Compare the max width of each subtree while traversing the tree
        # (in, pre, and post should all work for this problem)
        # while adding +1 for each depth level while traversing

        # Postorder Traversal: (left -> right -> root)
        #   - Explore left: get width of tree
        #   - Explore right: get width of tree
        #   - Process root: connect left and right subtrees via curr node by adding widths
        #   - Compare to global max
        #   - Create length for curr node by grabbing max between left and right

        # Global max 
        maxWidth = 0
        
        def dfs(node):

            # nonlocal says maxWidth refers to the variable in the outer enclosing scope, 
            # don't create a new local one
            # res.append doesn't reassign the variable, 
            # it mutates the object it points to, so the preorder traversal
            # doesn't need nonlocal
            nonlocal maxWidth

            # Base case: 
            # reached a leaf's child 'None', width value of a leaf is 0
            if not node:
                return 0
            
            # Explore left
            leftWidth = dfs(node.left)

            # Explore right
            rightWidth = dfs(node.right)
            
            # Process root: connect left and right subtrees via curr node by adding widths
            checkTreeAtNode = leftWidth + rightWidth

            # Check maxWidth
            # nonlocal avoids this creating a new local variable within inner curr scope
            maxWidth = max(maxWidth, checkTreeAtNode)

            # Pick a side to continuing adding to length
            rootWidth = 1 + max(leftWidth, rightWidth)
            return rootWidth
        
        # Start at root
        dfs(root)

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

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        # Tree Widths:
        # Compare the max width of each subtree while traversing the tree
        # while adding +1 for each depth level while traversing

        # Postorder Traversal: (left -> right -> root)
        #   - Explore left: get width and max diameter of subtree
        #   - Explore right: get width and max diameter of subtree
        #   - Process root: connect left and right subtrees via curr node by adding widths
        #   - Compare connected width to left and right max diameters
        #   - Create length for curr node by grabbing max between left and right

        def dfs(node):

            # Base case:
            # reached a leaf's child 'None', width and max diameter of a leaf is 0
            if not node:
                return (0, 0)
            
            # Explore left
            (leftWidth, leftMaxDiameter) = dfs(node.left)

            # Explore right
            (rightWidth, rightMaxDiameter) = dfs(node.right)
            
            # Process root: connect left and right subtrees via curr node by adding widths
            connectedTree = leftWidth + rightWidth
            
            # Check max diameter against connected width and subtree max diameters
            rootMaxDiameter = max(connectedTree, leftMaxDiameter, rightMaxDiameter)
            
            # Create length for curr node by grabbing max between left and right
            rootWidth = 1 + max(leftWidth, rightWidth)
            
            # Pass curr node width and max diameter up recursion calls
            return (rootWidth, rootMaxDiameter)

        # Start at root
        res = dfs(root)[1]

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

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
       
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right -> :
        # 2. Process -> root : validate if balanced, raise exception if imbalanced
        # Results: detect imbalance, short-circuit on first imbalance found

        def dfs(node):

            # Base case: 
            # Reached leaf node, height of 0
            if node == None:
                return 0
            
            # Grab left height
            leftHeight = dfs(node.left)

            # Grab right height
            rightHeight = dfs(node.right)
            
            # Check:
            # Unbalanced node has left and right heights that differ by more than 1,
            # if node is unbalanced, raise exception
            if abs(leftHeight - rightHeight) > 1:
                raise ValueError("unbalanced")
            
            # Node is balanced, 
            # grab height and pass up
            rootHeight = 1 + max(leftHeight, rightHeight)
            return rootHeight
        
        # Catch exception
        try:
            dfs(root)
            return True
        except ValueError:
            return False

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

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> : 
        #    validate subtree matches
        # 2. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        # Recursive abstraction call to validate if same tree
        def isSameTree(s, t):

            # Pre Order: Validate that root nodes match

            # If both nodes are Leaves, trees match
            if not s and not t:
                return True

            # If only one node is a leaf, trees don't match
            if not s or not t:
                return False

            # If node values don't match, trees don't match
            if s.val != t.val:
                return False
            
            # Nodes match:
            # Check the rest of children to ensure complete match
            leftRes = isSameTree(s.left, t.left)
            rightRes = isSameTree(s.right, t.right)
            completeTreeMatch = leftRes and rightRes
            return completeTreeMatch
        
        # Empty check:
        # Empty subtree always matches
        if not subRoot:
            return True

        # Empty check:
        # Empty root tree never matches non-empty subtree
        if not root:
            return False
        
        # Full Match:
        # Check if trees are a complete match
        if isSameTree(root, subRoot):
            return True
        
        # Subtree Match:
        # Check if trees are a complete match at some inner subtree
        else:
            leftRes = self.isSubtree(root.left, subRoot)
            rightRes = self.isSubtree(root.right, subRoot) 
            innerSubtreeMatch = leftRes or rightRes
            return innerSubtreeMatch

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

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        

        def preAndInArrayToTree(left, right):

            # Pre Order:
            # Holds the current root of the current tree we are building 
            nonlocal preIndex

            # Base case: 
            # no elements remaining, return leaf
            if left > right:
                return None

            # Use Pre Order pointer to grab root value
            root_val = preorder[preIndex]
            root = TreeNode(root_val)

            # Use root value, to grab root index relative to In Order array
            root_index = inorder_index_map[root_val]

            # [left ... root ... right]
            # the root index will always split the in order array into left and right subtrees

            # [left ... root - 1, root, root + 1 ... right]
            
            # So the left subtree gets the left section: [left ... root - 1]
            left_subtree_left = left
            left_subtree_right = root_index - 1

            # And the right subtree gets the right section: [root + 1 ... right]
            right_subtree_left = root_index + 1
            right_subtree_right = right

            # Iterate to next root from pre order (root -> left -> right),
            # so we build left and then right subtrees
            preIndex += 1

            # Recurse to assign the left and right subtree range
            root.left = preAndInArrayToTree(left_subtree_left, left_subtree_right)
            root.right = preAndInArrayToTree(right_subtree_left, right_subtree_right)

            # Use Pre Order pointer to grab the next root value
            return root


        # PreRootIndex: 
        #   - root of tree we currently building
        #   - trees will be build in order of pre order (root -> left -> right) 
        
        # Left/Right InOrderTreeBounds: 
        #   - left/right bounds of tree we are currnetly building
        #   - bounds will be in order of in order (left -> root -> right)

        # InOrderHashMap:
        #   - translates root from PreOrder be relative to InOrder, (left -> root -> right)

        # Tree Root Building Tracker:
        preIndex = 0

        # Left/Right Bounds Building Tracker:
        leftTreeBounds = 0 
        rightTreeBounds = len(inorder)-1

        # LookUp for (value -> index) for In Order Array
        inorder_index_map = {}
        for idx, val in enumerate(inorder):
            inorder_index_map[val] = idx

        # Start building tree from root
        fullTree = preAndInArrayToTree(leftTreeBounds, rightTreeBounds)

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

    def rob(self, root: Optional[TreeNode]) -> int:
                
        # House Tree Structure:
        # Each house is a node in a binary tree.
        # If we rob a node, we cannot rob its direct children.
        
        # Ex:
        #        5
        #       / \
        #      4   7
        #       \   \
        #        2   8
        
        # Key Idea (Tree DP):
        # At each node, we must decide between:
        #
        #   1. Rob this node
        #      -> Cannot rob left or right child
        #
        #   2. Skip this node
        #      -> We are allowed to either rob or skip children, 
        #         so we grab the max between two options
        #
        # Each node needs to return two states
        #   - rob
        #   - skip
        

        # Post Order traversal: (left -> right -> root)
        # We must process children first before calculating value for parent
        
        def dfs(node):
            
            # Base case: 
            # An empty node contributes nothing, mark its values are 0, 0 for rob/skip
            if not node:
                return (0, 0)
            
            # Postorder traversal
            leftRob, leftSkip = dfs(node.left)
            rightRob, rightSkip = dfs(node.right)
            
            # DP:
            # Need to generate the values for rob/skip for children of this node

            # Rob Node:
            # Grab value for node, skip both children
            robNode = node.val + leftSkip + rightSkip
            
            # Skip Node: 
            # Skip this node, grab max from each child (could be rob/skip)
            skipNode = max(leftRob, leftSkip) + max(rightRob, rightSkip)
            
            # Return both rob/skip DP states for this node
            return (robNode, skipNode)
        
        
        # Grab the rob/skip values for the root node
        (rootRob, rootSkip) = dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(h)
        return max(rootRob, rootSkip)

    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        
        # We only want remove LEAF nodes with value == target

        # Need to use Post Order (left -> right -> root),
        # as we can't decide if a Target Node is a leaf 
        # until we know if its children have been removed
        
        # Base case:
        # Current node is None, return None
        if not root:
            return None
        
        # Remove target nodes from left and right subtrees
        root.left = self.removeLeafNodes(root.left, target)        
        root.right = self.removeLeafNodes(root.right, target)
        
        # Remove current node if:
        #   - Node is a target value 
        #   - left and right are None, (current node is a leaf)
        if not root.left and not root.right and root.val == target:
            return None
        
        # overall: tc O(n)
        # overall: sc O(log n) for balanced / O(n) for skewed trees
        return root

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        # Negative Path 0 Flattening Reset Separating Positive Subtrees:
        #  - We have negative values in the tree,
        #    so we treat negative values are reset points for our sum paths.
        #    Clamp to 0 resets the path sum, 
        #    which breaks the tree into sections of only positive sums,
        #    so maxSum becomes the max positive path

        # Ex:
        #        1
        #       / \
        #     -2   5
        #    /  \   \
        #   6    2   8
        #    \
        #     3
        
        # Postorder Traversal (DFS): (left -> right -> root)
        #   - Need to process left and right subtrees 
        #     before to determine where the positive tree paths are

        # Global max path sum across all nodes
        maxSum = float('-inf')

        def dfs(node):
            nonlocal maxSum

            # Base case:
            # reached a leaf's child 'None'
            if not node:
                return 0

            # Clamp negative paths to 0, so we only consider positive paths
            leftGain = max(dfs(node.left), 0)
            rightGain = max(dfs(node.right), 0)

            # Connect left and right paths through current node
            currTree = node.val + leftGain + rightGain

            # Check global max
            maxSum = max(maxSum, currTree)

            # Continue passing up better branch upwards
            currMax = node.val + max(leftGain, rightGain)
            return currMax

        dfs(root)

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

    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        
        # Re-rooting DP:
        # common idea in competitive programming,
        # somewhat easy to spot as such problems typically ask something like
        # "find some value for each root"

        # Re-rooting DP (Dynamic Programming On Trees):
        # Challenge is the problem asks for answer at EVERY node,
        # pretending as if that node is the root, so:
        #   1. pick a node as root
        #   2. run a DFS to compute its answer
        #   3. repeat for the rest n nodes
        # Which would lead to O(n^2)

        # Re-rooting DP avoids recomputing everything from scratch and allows O(n)
        # We first compute the answer for one root (node 0),
        # then efficiently "move" the root across each edge

        # Key Point:
        # When moving the root from parent -> child:
        #   - child subtree nodes become 1 step closer
        #   - all other nodes become 1 step further

        # So using the previously computed DP values, we can derive
        # the child's answer in O(1) instead of running another DFS

        # General Pattern:
        #   Pass 1 (Postorder):
        #       - gather information from children -> parent

        #   Pass 2 (Preorder):
        #       - Propagate answers from parent -> children

        # Build undirected adjacency list
        # sc: O(n)
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)


        # Sum of distances from node 0 to all other nodes (postorder result):

        # After Pass 1:
        #   nodeToAllTotal[0] = answer for root node 0
        # After Pass 2:
        #   nodeToAllTotal[i] = answer for root node i
        # ex:
        #   nodeToAllTotal[3] = sum of distances from node 3 to all nodes
        # sc: O(n)
        nodeToAllTotal = [0] * n


        # Subtree sizes rooted starting at node 0 to all children
        
        # Ex:
        #        0
        #       / \
        #      1   2
        #         / \
        #        3   4
        #
        # count[2] = 3  (nodes 2,3,4)
        # count[0] = 5  (entire tree)

        # count[node] = size of nodes's subtree

        # Re-rooting needs subtree sizes because when we move
        # the root from parent -> child, we must know:
        #   - how many nodes get closer?
        #   - how many nodes get farther?

        # sc: O(n)
        subtreeSize = [1] * n

        # Pass 1: Postorder DFS
        # Solve the tree assuming node 0 is the root

        # Postorder Traversal (DFS): (left -> right -> root)
        #   - Process all children first, accumulate subtree sizes and distances
        def dfs_postOrder(node, parent):

            # First process children
            for leftOrRight in tree[node]:

                # Skip original parent to avoid cycles
                if leftOrRight == parent:
                    continue

                # Process child subtree first
                dfs_postOrder(leftOrRight, node)

                # Add children distances to parent
                subtreeSize[node] += subtreeSize[leftOrRight]

                # Sub distances from node = distances from child + all nodes in child subtree
                nodeToAllTotal[node] += nodeToAllTotal[leftOrRight] + subtreeSize[leftOrRight]


        # Pass 2: Preorder DFS
        # Having the answer for node 0, derive the answer for every other node

        # Preorder Traversal (DFS): (root -> left -> right)
        #   - Process root first, propagate re-rooted distances downward to children    
        def dfs_preOrder(node, parent):

            for leftOrRight in tree[node]:

                # Skip parent to avoid cycles
                if leftOrRight == parent:
                    continue

                # Re-root from node -> leftOrRight:
                # leftOrRight subtree (subtreeSize[leftOrRight] nodes) each get 1 closer
                # outside subtree (n - subtreeSize[leftOrRight] nodes) each get 1 further
                nodeToAllTotal[leftOrRight] = 
                    nodeToAllTotal[node] 
                    - subtreeSize[leftOrRight] 
                    + (n - subtreeSize[leftOrRight])

                # Propagate to leftOrRight's children
                dfs_preOrder(leftOrRight, node)


        # Pass 1: postorder — compute subtree sizes and distances from root 0
        dfs_postOrder(0, -1)

        # Pass 2: preorder — re-root and propagate distances to all nodes
        dfs_preOrder(0, -1)

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

    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:

        # Postorder Traversal (DFS): (left -> right -> root) + Greedy Tree Cutting
        #   - Process all children first, accumulate subtree sum
        #   - Process root: if subtree sum % k == 0, cut edge and count as component
        #   - Returning 0 to parent simulates cutting the edge (excludes from parent sum)
        #   - Greedy: cut as early (as deep) as possible to maximize components

        # Greedy Proof: cutting at the deepest valid point is always safe
        #
        # claim: if subtree_sum % k == 0, we can safely cut the edge to parent
        #        without affecting whether the parent sum is divisible by k
        #
        # proof:
        #   let parent_sum = parent's accumulated sum before adding this subtree
        #   let subtree_sum % k == 0  (our condition)
        #
        #   without cut: (parent_sum + subtree_sum) % k
        #                = (parent_sum % k + subtree_sum % k) % k
        #                = (parent_sum % k + 0) % k
        #                = parent_sum % k
        #
        #   with cut:    (parent_sum + 0) % k
        #                = parent_sum % k
        #
        #   both cases produce the same remainder at the parent
        #   - cutting never breaks a valid component higher up
        #   - greedy cut is always safe

        # Build undirected adjacency list
        # sc: O(n)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Global component count
        # sc: O(1)
        self.components = 0

        def dfs(node, parent):

            # Base case:
            # start subtree sum with current node's value
            subtree_sum = values[node]

            # Process left -> right ->
            # accumulate subtree sums from all children
            for nei in graph[node]:

                # Skip parent to avoid cycles
                if nei == parent:
                    continue

                subtree_sum += dfs(nei, node)

            # Process -> root: check if subtree is divisible by k
            if subtree_sum % k == 0:

                # Greedy: 
                # Cut immediately at the deepest valid point.
                # Cutting early is always safe, if a subtree sum is divisible by k,
                # including it in the parent can never create more components than cutting it now
                # proof: parent_sum % k is unchanged whether we add (subtree_sum) or (0)
                #        since subtree_sum % k == 0, both contribute the same remainder
                self.components += 1

                # Return 0 to parent to simulate cutting the edge
                return 0

            # Subtree not divisible — pass sum up to parent
            return subtree_sum

        # Start DFS from root
        dfs(0, -1)

        # overall: tc O(n)
        # overall: sc O(n)
        return self.components

    def construct(self, grid: List[List[int]]) -> 'Node':

        # Recursive Quad-Tree Construction (Divide and Conquer)
        #   - Divide grid into 4 equal sub-grids, recurse on each
        #   - Process children first (postorder), then merge at root
        #   - If all 4 children are leaves with the same value, merge into one leaf
        #   - Otherwise create an internal node with 4 children

        # Grid size
        # sc: O(1)
        n = len(grid)

        def dfs(r0: int, c0: int, size: int) -> Node:

            # Base case:
            # 1x1 grid is always a leaf
            if size == 1:
                return Node(val=bool(grid[r0][c0]), isLeaf=True)

            # Divide grid into 4 equal sub-grids
            half = size // 2

            # Process all 4 children first (postorder)
            topLeft     = dfs(r0,        c0,        half)
            topRight    = dfs(r0,        c0 + half, half)
            bottomLeft  = dfs(r0 + half, c0,        half)
            bottomRight = dfs(r0 + half, c0 + half, half)

            # Process -> root: check if all children are leaves with same value
            all_leaves    = all(child.isLeaf for child in [topLeft, topRight, bottomLeft, bottomRight])
            all_same_val  = topLeft.val == topRight.val == bottomLeft.val == bottomRight.val

            # Merge into single leaf — uniform subgrid
            if all_leaves and all_same_val:
                return Node(val=topLeft.val, isLeaf=True)

            # Cannot merge — create internal node with 4 children
            return Node(
                val=True,
                isLeaf=False,
                topLeft=topLeft,
                topRight=topRight,
                bottomLeft=bottomLeft,
                bottomRight=bottomRight
            )

        # Start recursive construction from full grid
        dfs(0, 0, n)

        # overall: tc O(n^2)
        # overall: sc O(log n)
        return dfs(0, 0, n)