def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Inorder Traversal (DFS): left -> root -> right
        # Idea:
        #   1. Process left subtree recursively
        #   2. Visit current root node and append value
        #   3. Process right subtree recursively
        
        result = []
        
        def dfs(node: Optional[TreeNode]):
            # Base case: reached leaf node's child (None)
            if not node:
                return
            
            # Traverse left subtree first
            dfs(node.left)
            
            # Visit current node
            result.append(node.val)
            
            # Traverse right subtree next
            dfs(node.right)
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(h), where h is height of tree (O(log n) balanced, O(n) skewed)
        return result

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Iterative Inorder Traversal using a Stack
        # Idea:
        #   1. Use a stack to simulate recursion
        #   2. Go as left as possible, pushing nodes onto stack
        #   3. Pop from stack, visit node, then move to right child
        
        result = []
        stack = []
        current = root
        
        # Traverse until there are no nodes left to process
        while current or stack:
            
            # Go as left as possible, push all left nodes to stack
            while current:
                stack.append(current)
                current = current.left
            
            # Pop the leftmost node (smallest value in subtree)
            current = stack.pop()
            
            # Visit current node
            result.append(current.val)
            
            # Move to right subtree
            current = current.right
        
        # overall: tc O(n)
        # overall: sc O(h + n), O(h) for stack, O(n) for result array
        return result

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Recursive Preorder Traversal (DFS): root -> left -> right
        # Idea:
        #   1. Visit current root node first
        #   2. Recursively traverse left subtree
        #   3. Recursively traverse right subtree
        
        result = []
        
        def dfs(node: Optional[TreeNode]):
            # Base case: reached leaf's child (None)
            if not node:
                return
            
            # Visit current node
            result.append(node.val)
            
            # Traverse left subtree
            dfs(node.left)
            
            # Traverse right subtree
            dfs(node.right)
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(h), where h = tree height (O(log n) balanced, O(n) skewed)
        return result

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
                
        # Iterative Preorder Traversal using a Stack
        # Idea:
        #   1. Use a stack to process nodes in root -> left -> right order
        #   2. Pop node from stack, visit it
        #   3. Push right child first, then left child so left is processed first
        
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            # Pop current node
            node = stack.pop()
            
            # Visit current node
            result.append(node.val)
            
            # Push right child first so left is processed first
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        
        # overall: tc O(n)
        # overall: sc O(h + n), O(h) for stack, O(n) for result array
        return result

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        # Recursive Postorder Traversal (DFS): left -> right -> root
        # Idea:
        #   1. Recursively traverse left subtree
        #   2. Recursively traverse right subtree
        #   3. Visit current root node last
        
        result = []
        
        def dfs(node: Optional[TreeNode]):
            # Base case: reached leaf's child
            if not node:
                return
            
            # Traverse left subtree
            dfs(node.left)
            
            # Traverse right subtree
            dfs(node.right)
            
            # Visit current node
            result.append(node.val)
        
        # Start DFS from root
        dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(h), where h = tree height (O(log n) balanced, O(n) skewed)
        return result

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        
        # Iterative Postorder Traversal using a Stack
        # Idea:
        #   1. Postorder is left -> right -> root
        #   2. Use a modified preorder: root -> right -> left
        #   3. Reverse the result at the end to get correct postorder
        
        if not root:
            return []
        
        stack = [root]
        result = []
        
        while stack:
            node = stack.pop()
            # Visit node first (root in modified preorder)
            result.append(node.val)
            
            # Push left first, then right to process right first
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        
        # Reverse the result to get left -> right -> root
        result.reverse()
        
        # overall: tc O(n)
        # overall: sc O(h + n), O(h) for stack, O(n) for result array
        return result

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        # Tree:
        # A tree is made up of nodes which point to other nodes
        # They must have pointers and they may or may not have values:
        #      ()             1
        #      / \           / \
        #    ()   ()        2   3 
        #         / \           / \
        #       ()   ()        4   5

        # To find the width of a tree, we simply have to compare
        # the max width of each subtree at each root node, 
        # and keep track of the max width found, while adding +1
        # to account for the current root node

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: get width of tree
        #   2. Process right node: get width of tree
        #   3. Process root node: compare max width between left and right, add +1

        globalDiameter = 0
        
        def dfs(node):
            nonlocal globalDiameter

            # Empty check
            if not node:
                return 0
            
            # Process left -> right ->
            left_len = dfs(node.left)
            right_len = dfs(node.right)
            
            # Process -> root : connect left and right subtrees
            connected_at_root = left_len + right_len

            # Update max diameters: 
            globalDiameter = max(globalDiameter, connected_at_root)

            # Process -> root: add edge between root -> parent
            root_len = 1 + max(left_len, right_len)

            return root_len
        
        # recursive process root
        dfs(root)

        # overall: time complexity
        # overall: space complexity
        return globalDiameter

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right :
        # 2. Process -> root : connect left and right subtrees, get root max diameter
        # Result: longest path of edges

        def dfs(node):

            # Empty check
            if not node:
                return (0, 0)
            
            # process left -> right -> :
            (left_len, left_max_diameter) = dfs(node.left)
            (right_len, right_max_diameter) = dfs(node.right)
            
            # process -> root : connect left and right subtrees
            connected_at_root = left_len + right_len
            
            # Update max diameters
            root_max_diameter = max(connected_at_root, left_max_diameter, right_max_diameter)
            
            # Process -> root: add edge between root -> parent
            root_len = 1 + max(left_len, right_len)
            
            return (root_len, root_max_diameter)
        
        # overall: time complexity
        # overall: space complexity
        return dfs(root)[1]

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        
        # Empty check
        if not root:
            return 0
        
        max_diameter = 0
        
        # iterative stack
        stack = []

        # store results 
        depth_map = defaultdict(int)
        last_visited = None
        node = root

        while stack or node:
            
            # process left -> 
            # 
            while node:
                stack.append(node)
                node = node.left
            
            # check if right subtree exists
            peek = stack[-1]

            # process -> right -> 
            # if right subtree exists and not visited yet:
            if peek.right and last_visited != peek.right:
                node = peek.right
            
            # process -> root : (after subtrees)
            else:
                # remove from stack
                stack.pop()

                # results from subtrees
                left_depth = depth_map[peek.left]
                right_depth = depth_map[peek.right]

                # process -> root : Update diameter with path through current node
                max_diameter = max(max_diameter, left_depth + right_depth)

                # process -> root : get diameter of root
                depth_map[peek] = 1 + max(left_depth, right_depth)

                # update last visited to current
                last_visited = peek

        # overall: time complexity
        # overall: space complexity
        return max_diameter

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

        # Empty check
        if not root:
            return 0

        # dictionary: node -> (tree max diameter, tree length)
        node_data = defaultdict(lambda: (0, 0))

        # iterative stack
        stack = []

        curr = root
        last_visited = None

        while stack or curr:
            
            # Process left -> : 
            while curr:
                stack.append(curr)
                curr = curr.left

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

            # Process -> right -> 
            # if right subtree exists and had not been visited:
            if peek.right and last_visited != peek.right:
                curr = peek.right

            # Process -> root
            else:
                # remove root from stack
                stack.pop()

                # grab results from subtrees
                left_edges, left_bridge = node_data[peek.left]
                right_edges, right_bridge = node_data[peek.right]

                # bridge by connecting left and right edges
                connected_bridge = left_edges + right_edges

                # max bridge between new bridge, max left bridge, and max right bridge
                root_max_bridge = max(connected_bridge, left_bridge, right_bridge)

                # length/edges at current root
                root_edges = 1 + max(left_edges, right_edges)

                # update data for current root
                node_data[peek] = (root_edges, root_max_bridge)

                # update last visited
                last_visited = peek
                
        return node_data[root][1]

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right -> :
        # 2. Process -> root : validate if balanced, throw -1 imbalance error
        # Results: detect imbalance

        def dfs(node):

            # Base case: pass height upwards
            if not node:
                return 0
            
            # process left -> right ->
            left_height = dfs(node.left)
            right_height = dfs(node.right)

            # pass thrown error upwards
            if left_height == -1 or right_height == -1:
                return -1         
            
            # process -> root : validate balanced left and right subtrees
            if abs(left_height - right_height) > 1:
                return -1
            
            root_height = 1 + max(left_height, right_height)

            # process -> root : add to height and pass to root's parent
            return root_height
        
        # overall: time complexity
        # overall: space complexity
        return dfs(root) != -1

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right ->
        # 2. Process -> root : validate if balanced, pass invalid tuple error
        # Results: detect imbalance
        
        def dfs(node):

            # Base case: leaf -> (balanced:True, height:0)
            if not node:
                return (0, True)
            
            # Process left -> right -> (is_balanced, height)
            (left_height, left_bal) = dfs(node.left)
            (right_height, right_bal) = dfs(node.right)

            # pass thrown error upwards
            if not left_bal or not right_bal:
                return (-1, False)
            
            # process -> root : validate balanced left and right subtrees
            is_root_balanced = abs(left_height - right_height) <= 1

            # process -> root : add to height and pass to root's parent
            root_height = 1 + max(left_height, right_height)

            return (root_height, is_root_balanced)
        
        # overall: time complexity
        # overall space complexity
        return dfs(root)[1]

    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

        # helper func 
        def isSameTree(s, t):

            # process root -> : 
            if not s and not t:
                return True

            # process root -> :
            if not s or not t:
                return False

            # process root -> :
            if s.val != t.val:
                return False
            
            # process -> left -> right :
            left_match = isSameTree(s.left, t.left)
            right_match = isSameTree(s.right, t.right)

            # process -> left -> right:
            subTreeMatch = left_match and right_match

            return subTreeMatch
        

        # Empty check
        if not subRoot:
            return True

        # Empty check
        if not root:
            return False
        
        # process root -> : 
        if isSameTree(root, subRoot):
            return True
        
        # process -> left -> right :
        tree_left_subtree_match = self.isSubtree(root.left, subRoot)
        tree_right_subtree_match = self.isSubtree(root.right, subRoot) 

        # process -> left -> right :
        tree_match = tree_left_subtree_match or tree_right_subtree_match

        # overall: time complexity
        # overall: space complexity
        return tree_match

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Note:
        # BFS order: level by level : root -> left -> right
        # 1. For each level:
        # 2. Process root -> : 
        #    if root values match, run isSameTree
        # 3. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        def isSameTree(s, t):

            # Process root -> :
            if not s and not t:
                return True

            # Process root -> : 
            if not s or not t:
                return False  

            # Process root -> : 
            if s.val != t.val:
                return False
            
            # Process -> left -> right :
            left_match = isSameTree(s.left, t.left)
            right_match = isSameTree(s.right, t.right)

            # Process -> left -> right :
            subtree_match = left_match and right_match

            return subtree_match

        # Empty check:
        if not subRoot:
            return True

        # Empty check:
        if not root:
            return False
        
        # iterative queue
        queue = deque([root])

        while queue:

            # Process root -> :
            root_node = queue.popleft()

            # Process root -> : if match, test with isSameTree
            if root_node.val == subRoot.val and isSameTree(root_node, subRoot):
                return True

            # Process -> left -> right :
            if root_node.left:
                queue.append(root_node.left)
            if root_node.right:
                queue.append(root_node.right)
        
        # overall: time complexity
        # overall: space complexity
        return False

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #      serialize values with leading comma
        #      ("2" in "12" would match incorrectly without boundaries, so comma needed)
        #      ",2"
        # 2. Process -> left -> right :
        # Result: validate if subtree is subtree of tree

        def serialize(node):
            
            # process root -> :
            if not node:
                return ",N"

            # process root -> :
            root_serial = node.val

            # process -> left -> right :
            left_serial = serialize(node.left)
            right_serial = serialize(node.right)

            # process root -> :
            subTree_serial = f",{node.val}{left_serial}{right_serial}" 

            return subTree_serial

        # process root -> :
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)

        # process root -> :
        subTree_match = serializedSubRoot in serializedRoot

        # overall: time complexity
        # overall: space complexity
        return subTree_match

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        def serialize(node):
            if not node:
                return ",N"

            # In-order: left -> root -> right
            left_serial = serialize(node.left)
            root_val = f",{node.val}"
            right_serial = serialize(node.right)
            
            subtree_serial = f"#{left_serial}@{root_val}${right_serial}^"
            return subtree_serial

        
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)
        
        # Check if serializedSubRoot is a substring of serializedRoot
        match = serializedSubRoot in serializedRoot

        # overall: time complexity
        # overall: space complexity
        return match

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def serialize(node):
            # Base case: null marker for missing child
            if not node:
                return ",N"
            
            # Postorder: left -> right -> root
            
            left_serial = serialize(node.left)
            right_serial = serialize(node.right)
            
            # Append root after left and right serialization
            subTree_serial = f"#{left_serial}@{right_serial},{node.val}^"            
            return subTree_serial
        
        serializedSubRoot = serialize(subRoot)
        serializedRoot = serialize(root)
        
        # Check if serializedSubRoot is a substring of serializedRoot
        match = serializedSubRoot in serializedRoot 

        # overall: time complexity
        # overall: space complexity
        return match   

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

        # Tree:
        #        1
        #       / \
        #      2   3
        #     / \   \
        #    4   5   6
        #             \
        #              7
    
        # Pre order: root -> left -> right
        # [1, 2, 4, 5, 3, 6, 7]

        # In order: left -> root -> right 
        # [4, 2, 5, 1, 3, 6, 7]

        # Note:
        # Pre order: current root supplier
        # by iterating over this: root -> left -> right

        # In order: recursive range provider
        # due to Invariant from: left -> root -> right
        # for all roots -> [ leftSubtree, root, rightSubtree ]

        # val -> in order array index
        inorder_index_map = {val: idx for idx, val in enumerate(inorder)}

        # iterating over pre order: the current root supplier, 
        # will determine which tree we are currently building
        pre_idx = 0


        # recurse over in order list 
        def array_to_tree(left, right):
            nonlocal pre_idx

            # Base case: no elements to construct subtree
            if left > right:
                return None

            # 1. curr 'root': root -> left -> right
            root_val = preorder[pre_idx]
            
            # prepare next root ('left'): above becomes -> left -> right
            pre_idx += 1

            # Create root node
            root = TreeNode(root_val)

            # 2: Find root's index for in order 
            #    to trigger invariant [leftSubtree, root, rightSubtree]
            root_index = inorder_index_map[root_val]

            # 3: given invariant, 
            #    trigger left subtree range for in order array
            left_subtree_left = left
            left_subtree_right = root_index - 1

            # 4: given invariant, 
            #    trigger right subtree range for in order array
            right_subtree_left = root_index + 1
            right_subtree_right = right

            # 5: pass left subtree range
            root.left = array_to_tree(left_subtree_left, left_subtree_right)

            # 5: pass] right subtree range
            root.right = array_to_tree(right_subtree_left, right_subtree_right)

            # root with subtrees
            return root

        # initialize bounds for topmost root
        left_start = 0 
        right_start = len(inorder)-1

        # recurse starting at topmost root, 
        # rest of tree created by recursion (magic)
        orig_tree = array_to_tree(left_start, right_start)

        # overall: time complexity
        # overall: space complexity 
        return array_to_tree(left_start, right_start)

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

        # Tree:
        #        1
        #       / \
        #      2   3
        #     / \   \
        #    4   5   6
        #             \
        #              7
    
        # Pre order: root -> left -> right
        # [1, 2, 4, 5, 3, 6, 7]

        # In order: left -> root -> right 
        # [4, 2, 5, 1, 3, 6, 7]

        # Empty check
        if not preorder or not inorder:
            return None
        
        # 1: topmost root -> preorder[0]
        #.   iterate over preorder, create and connect with parent
        root = TreeNode(preorder[0])

        # 2: stack: 
        #    filled by iterative preorder root -> left -> right
        #    holds roots that are waiting for subtrees
        stack = [root]

        # 2: inorder_index:
        #  start at bottom left most subtree 0
        inorder_index = 0

        # In order invariant -> [leftSubtree, root, rightSubtree]
        # when inorder index pointing to some root:
        #   1) root has no left subtrees
        #   2) root's left subtrees have been created and assigned

        # 3: iterate over preorder: root -> left -> right
        for i in range(1, len(preorder)):

            # peek top of stack:
            # previous node waiting for subtrees
            top = stack[-1]

            # pre order: subtree of top
            preorder_val = preorder[i]
            
            # in order: left most complete root
            inorder_val = inorder[inorder_index]

            # if top of stack is not complete
            # preorder is the tops left subtree
            if top.val != inorder_val:

                # connect and push to stack,
                # to find left subtrees subtrees
                top.left = TreeNode(preorder_val)
                stack.append(top.left)
                        
            # if top of stack is complete
            # preorder is the tops right subtree
            else:
                
                # now we have arrive to top most root,
                # if in order marks as complete, that means there ar
                while stack and stack[-1].val == inorder[inorder_index]:
                    top = stack.pop()
                    inorder_index += 1
                
                # process -> right :
                # preorder_val is a right child, connect and push to stack
                top.right = TreeNode(preorder_val)
                stack.append(top.right)
        
        # overall: time complexity
        # overall: space complexity
        return root

    def rob(self, root: Optional[TreeNode]) -> int:
        
                
        # Tree Structure:
        # Each house is a node in a binary tree.
        # Constraint:
        # If we rob a node, we cannot rob its direct children.
        
        # Example:
        #        3
        #       / \
        #      2   3
        #       \   \
        #        3   1
        
        # Key Idea (Tree DP):
        # At each node, we must decide between:
        #
        #   1. Rob this node
        #      -> Cannot rob left child
        #      -> Cannot rob right child
        #
        #   2. Skip this node
        #      -> We are free to rob or skip children
        #
        # Therefore, each node returns TWO values:
        #
        #   (rob_this_node, skip_this_node)
        #
        # Postorder traversal:
        # left -> right -> root
        # We must process children first before deciding parent.
        
        
        def dfs(node: Optional[TreeNode]):
            
            # Base case: empty node contributes nothing
            if not node:
                # (rob, skip)
                # tc O(1), sc O(1)
                return (0, 0)
            
            # Postorder traversal
            left_rob, left_skip = dfs(node.left)
            right_rob, right_skip = dfs(node.right)
            
            # Case 1: Rob this node
            # If we rob current node,
            # we must skip both children
            rob_this = node.val + left_skip + right_skip
            
            # Case 2: Skip this node
            # If we skip current node,
            # we can take the best option from each child
            skip_this = max(left_rob, left_skip) + \
                        max(right_rob, right_skip)
            
            # Return both states upward
            # tc per node O(1)
            return (rob_this, skip_this)
        
        
        result = dfs(root)
        
        # Final decision:
        # We can either rob root or skip root
        # overall: tc O(n)
        # overall: sc O(h), recursion stack depth
        return max(result)

    def removeLeafNodes(self, root: Optional[TreeNode], target: int) -> Optional[TreeNode]:
        
        # Problem:
        # Delete all leaf nodes with value == target.
        #
        # Important:
        # After deleting a leaf node,
        # its parent may become a new leaf.
        # If that parent also equals target,
        # it must be deleted as well.
        #
        # Therefore:
        # We must process children BEFORE deciding about parent.
        #
        # This is a classic Postorder traversal:
        # left -> right -> root
        #
        # Why Postorder?
        # Because whether a node becomes a leaf depends
        # on what happens to its children.
        
        
        # Base case: empty tree
        if not root:
            return None
        
        # Postorder step 1: process left subtree
        root.left = self.removeLeafNodes(root.left, target)
        
        # Postorder step 2: process right subtree
        root.right = self.removeLeafNodes(root.right, target)
        
        # Postorder step 3: decide whether to delete current node
        #
        # A node should be deleted if:
        #   1. It is a leaf (no children)
        #   2. Its value equals target
        
        if not root.left and not root.right and root.val == target:
            # Delete this node by returning None to parent
            # tc O(1), sc O(1)
            return None
        
        # Otherwise keep the node
        # tc: O(n) total (each node visited once)
        # sc: O(h) recursion stack depth
        return root

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process left -> right -> :
        # 2. Process -> root :
        #     

        # global max
        max_sum = float('-inf')

        def dfs(node):
            nonlocal max_sum

            # Empty check
            if not node:
                return 0

            # Process left -> right -> 
            left_gain = max(dfs(node.left), 0)
            right_gain = max(dfs(node.right), 0)

            # Process -> root :
            connected_at_root = node.val + left_gain + right_gain

            # Process -> root : check global max
            max_sum = max(max_sum, connected_at_root)

            # Process -> root : get max path at root
            root_max_path = node.val + max(left_gain, right_gain)

            return root_max_path

        dfs(root)

        # overall: time complexity
        # overall: space complexity
        return max_sum

    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        
        # Build tree adjacency list
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)

        res = [0] * n        # result: sum of distances for each node
        count = [1] * n      # subtree sizes (initialize to 1 for self)

        # Post-order DFS:
        def dfs1(node, parent):
            for child in tree[node]:
                if child == parent:
                    continue
                dfs1(child, node)
                count[node] += count[child]
                res[node] += res[child] + count[child]

        # Pre-order DFS:
        def dfs2(node, parent):
            for child in tree[node]:
                if child == parent:
                    continue
                # Shift root from node -> child
                res[child] = res[node] - count[child] + (n - count[child])
                dfs2(child, node)

        dfs1(0, -1)  # post-order: compute subtree sizes and partial sums
        dfs2(0, -1)  # pre-order: propagate distances to children

        return res

    def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
        
        # DFS + BST Optimization
        #
        # Idea:
        #   - Use BST property to prune entire subtrees.
        #
        # Rules:
        #   1. If node.val < low:
        #        - left subtree is invalid
        #        - return trimmed right subtree
        #
        #   2. If node.val > high:
        #        - right subtree is invalid
        #        - return trimmed left subtree
         
        #   3. Otherwise:
        #        - node is valid
        #        - recursively trim both children
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(h) (recursion stack)

        if not root:
            return None

        # Node too small → discard left side
        if root.val < low:
            return self.trimBST(root.right, low, high)

        # Node too large → discard right side
        if root.val > high:
            return self.trimBST(root.left, low, high)

        # Node is valid → trim children
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        return root

    def maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:
        # DFS + Greedy Tree Cutting
        #
        # Idea:
        #   - Post-order DFS computes subtree sums.
        #   - If subtree sum % k == 0:
        #         -> count one component
        #         -> return 0 to parent (cut edge)
        #
        # Complexity:
        #   - Time: O(n)
        #   - Space: O(n)

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

        components = 0

        # ----------------------
        # Post-order DFS
        # ----------------------
        def dfs(node, parent):
            nonlocal components

            subtree_sum = values[node]

            for nei in graph[node]:
                if nei == parent:
                    continue

                subtree_sum += dfs(nei, node)

            # If divisible -> create component
            if subtree_sum % k == 0:
                components += 1
                return 0   # cut here

            return subtree_sum

        dfs(0, -1)

        return components

    def construct(self, grid: List[List[int]]) -> 'Node':
        
        # Recursive Quad-Tree Construction
        # Idea:
        #   1. Check if current subgrid is uniform (all 0s or all 1s)
        #   2. If uniform:
        #       - Create a leaf node with val = value
        #   3. If not uniform:
        #       - Create an internal node (isLeaf = False)
        #       - Divide grid into 4 equal sub-grids
        #       - Recursively construct children
        
        n = len(grid)
        
        def dfs(r0: int, c0: int, size: int) -> Node:
            # Base case: 1x1 grid is always a leaf
            if size == 1:
                # Leaf node with single value
                # tc O(1), sc O(1)
                return Node(val=bool(grid[r0][c0]), isLeaf=True)
            
            half = size // 2
            # Recurse for four sub-grids
            topLeft = dfs(r0, c0, half)
            topRight = dfs(r0, c0 + half, half)
            bottomLeft = dfs(r0 + half, c0, half)
            bottomRight = dfs(r0 + half, c0 + half, half)
            
            # Check if all four children are leaves with same value
            children = [topLeft, topRight, bottomLeft, bottomRight]
            if all(child.isLeaf for child in children) and \
               topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:
                # Merge into a single leaf
                # tc O(1), sc O(1)
                return Node(val=topLeft.val, isLeaf=True)
            else:
                # Create internal node with four children
                # tc O(1), sc O(1)
                return Node(val=True, isLeaf=False, 
                            topLeft=topLeft, topRight=topRight, 
                            bottomLeft=bottomLeft, bottomRight=bottomRight)
        
        # Start recursive DFS from full grid
        # overall: tc O(n^2), sc O(log n) recursion stack
        return dfs(0, 0, n)