4
      /   \
     2     5
    / \
   1   3

DFS visit order: 4 → 2 → 1 → 3 → 5
(go as deep as possible before backtracking)

        4
      /   \
     2     5
    / \
   1   3

DFS visit order: 1 → 2 → 3 → 4 → 5
(visit left subtree, then root, then right subtree)

        4
      /   \
     2     5
    / \
   1   3

DFS visit order: 1 → 3 → 2 → 5 → 4
(visit left subtree, then right subtree, then root)

    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

    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {

            // 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

            vector<int> res;

            dfs(root, res);

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

    private:
        void dfs(TreeNode* node, vector<int>& res) {

            // Base case:
            // reached a leaf's child 'nullptr'
            if (node == nullptr) {
                return;
            }

            // In order requires to explore root first, 'Visit' node
            res.push_back(node->val);

            // Recurse into left node
            dfs(node->left, res);

            // Recurse until exhausted

            // Finished exploring left, now explore right
            dfs(node->right, res);

            // Repeat
        }
    };

    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

            # 2 Match Cases:
            #   - both are laves
            #   - values match

            # 2 Failure Cases:
            #   - only one is a leaf
            #   - values do not match
            
            if s == None and t == None:
                return True
            if s == None or t == None:
                return False
            if s.val != t.val:
                return False
            
            # Match:
            # Validate the rest of children to ensure a full match
            return isSameTree(s.left, t.left) and isSameTree(s.right, t.right)
        
        # Empty check:
        # An empty subtree matches any tree
        if subRoot == None:
            return True

        # Empty check:
        # Nothing can match an empty root tree
        if root == None:
            return False
        
        # Full Match:
        # Check if trees are a complete match starting at root of original
        if isSameTree(root, subRoot):
            return True
        
        # Subtree Match:
        # Check if trees are a complete match at some inner subtree of original
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)  

        # overall: tc O(n * m)
        # overall: sc O(h1 + h2)

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        # Note:
        # DFS post order: left -> right -> root
        # 1. Process -> left -> right :
        #    hash children first (bottom up)
        # 2. Process root -> :
        #    combine children hashes into node hash (Merkle style)
        # Result: if subRoot hash appears anywhere in root's hash set, its a subtree

        import hashlib

        # Hash set to store all subtree hashes in root,
        # will be used to compare subtree vs merkle tree of original full tree
        # sc: O(n)
        rootHashes = set()

        # Recursive abstraction call to hash a subtree bottom up
        # tc: O(n)
        # sc: O(n)
        def merkleHash(node, addToRootHash):

            # Post Order: Hash children before hashing root

            # Base case:
            # Null node gets a consistent null sentinel hash
            if node == None:
                return "#"
            
            # Post Order: Hash children first (bottom up)
            leftHash  = merkleHash(node.left, addToRootHash)
            rightHash = merkleHash(node.right, addToRootHash)

            # Combine children hashes + node value into single hash
            # Delimiters prevent value collision (e.g. val 1,2 vs val 12)
            nodeSignature = f"{leftHash},{node.val},{rightHash}"
            nodeHash = hashlib.md5(nodeSignature.encode()).hexdigest()

            # This subtree's hash belongs to original root tree
            if addToRootHash:
                rootHashes.add(nodeHash)

            return nodeHash
        
        # Build all subtree hashes for root (bottom up)
        merkleHash(root, True)

        # Build subRoot hash using same hashing logic
        subRootHash = merkleHash(subRoot, False)

        # Check if subRoot fingerprint exists anywhere in root
        res = subRootHash in rootHashes

        # overall: tc O(n + m)
        # overall: sc O(n + m)
        return res

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
            
        # Pre Order + In Order Array (no null markers):

        # To reconstruct the tree we need to solve these two requirements:
        #   - "where does the root sit"
        #   - "where does each subtree end" (i.e. the left/right split)

        # Pre Order + In Order or Post Order + In Order 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.
        #   - In order + known root, the root being provided from Pre/post order, solves 
        #     "everything to the left of root belongs to the left subtree and vice versa for right" 
        #   - (So for this problem), Pre/post order + in order is fully self-sufficient as we get
        #     a fixed root position through pre order and explicit subtree boundaries through in order

        #   - (for contrast) 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.


        # Note:
        # We are given 2 arrays, pre order and in order, which are traversals of the same tree.
        # The pre order array will pointer will represent the root of the tree
        # The in order will represent the left and right subtrees of that root
        
        #         1
        #        / \
        #       2   3
        #      / \
        #     4   5

        # preorder (root -> left -> right):  [1, 2, 4, 5, 3]
        # inorder  (left -> root -> right):  [4, 2, 5, 1, 3]

        # 1. Grab root value from pre order pointer
        # 2. Since the values are unique, we can use root value to find root index in in order array
        # 3. The root index in the in order array will split the in order array into left and right subtrees
        # 4. We will then recursively build the left and right subtrees using the left and right sections of the in order array
        # 5. Move the pre order pointer to the next root which because (root -> left -> right),
        #    will be the left and right subtrees we just marked into sections

        # Recursive abstraction to build tree from pre and in order arrays
        # left and right are relative to the in order array, 
        # and represent the bounds of the current subtree we are building
        def preAndInArrayToTree(left, right):

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

            # Base case: 
            # no elements remain for in order, return leaf
            if left > right:
                return None

            # 1. Grab root value from pre order pointer
            rootVal = preorder[preIndex]
            root = TreeNode(rootVal)

            # 2. Since the values are unique, we can use root value to find root index in in order array
            rootIndex = inOrderIndexMapping[rootVal]

            # 3. The root index in the in order array will split the in order array into left and right subtrees

            # [left ... root ... right]  =>

            # [left ... root - 1, root, root + 1 ... right]
            #   | left subtree |   r     | right subtree |
            
            # Left subtree gets the left section: [left ... root - 1]
            leftSubtreeLeftNode = left
            leftSubtreeRightNode = rootIndex - 1

            # Right subtree gets the right section: [root + 1 ... right]
            rightSubtreeLeftNode = rootIndex + 1
            rightSubtreeRightNode = right

            # Iterate to next root from pre order (root -> left -> right),
            # so the left and right subtrees we just marked are about to be built
            preIndex += 1

            # 4. We will then recursively build the left and right subtrees using the left and right sections of the in order array

            # Recurse to assign the left and right subtree range
            root.left = preAndInArrayToTree(leftSubtreeLeftNode, leftSubtreeRightNode)
            root.right = preAndInArrayToTree(rightSubtreeLeftNode, rightSubtreeRightNode)

            # 5. Move the pre order pointer to the next root
            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 currently 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
        inOrderIndexMapping = {}
        for idx, val in enumerate(inorder):
            inOrderIndexMapping[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)
        # Grab best choice from children to calculate best choice for root

        def dfs(node):
            
            # Base case: 
            # A leaf node has no value, 
            # mark both the rob and skip values as 0
            if not node:
                return (0, 0)
            
            # Post Order traversal
            # grab value for rob and skip from children
            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 and skip children
            robNode = node.val + leftSkip + rightSkip
            
            # Skip node and max between rob or skip children 
            skipNode = max(leftRob, leftSkip) + max(rightRob, rightSkip)
            
            # Return rob and skip values for node
            return (robNode, skipNode)
        
        
        # Grab the rob/skip values for the root node
        (rootRob, rootSkip) = dfs(root)
        
        # overall: tc O(n)
        # overall: sc O(log(n)) for balanced / O(n) for skewed trees
        return max(rootRob, rootSkip)

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

        # Post Order (left -> right -> root):
        # Remove children first and determine if root will become a leaf
        
        # Base case:
        # Nothing to remove
        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:
        #   - left and right are None, (current node is a leaf)
        #   - Node has the target value 
        if root.left == None and root.right == None 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 findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # DFS Post Order Height Bucketing

        # Track nodes height during DFS iteration
        # and bucket node's value into result[height] bucket as we go

        # Height buckets
        # sc: O(n)
        res = []

        def dfs(node) -> int:

            # Base Case:
            # a null child has no height, 
            # pass back -1 so that the parent leaf is assigned height 0
            if not node:
                return -1

            # Height of children
            leftHeight = dfs(node.left)
            rightHeight = dfs(node.right)

            # Compute Height:
            # 1 + the larger distance to a leaf between the two subtrees
            height = 1 + max(leftHeight, rightHeight)

            # Bucket Placement:
            # ensure height has a bucket before appending
            if height == len(result):
                res.append([])
            res[height].append(node.val)

            # Return heigh to root node 
            return height

        # Start height bucketing on root
        dfs(root)

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

    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

        # Positive Splits:
        #
        # [1, 5, 8], [2], [6, 3]
        
        # Postorder Traversal (DFS): (left -> right -> root)
        #   - Need to process left and right subtrees 
        #     before to determine where the positive tree paths are

        # Dynamic Programming:
        #   - DP state: dp[node] = max downward path sum starting at node,
        #     extending into ONE child branch (a path can only pass through
        #     a node once, so it can't fork into both children and still
        #     extend upward to the parent)
        #   - Transition: dp[node] = node.val + max(0, dp[left], dp[right])
        #   - Base case: dp[None] = 0
        #   - Each dp[node] is computed exactly once (postorder = correct
        #     evaluation order, since dp[node] needs dp[left]/dp[right] first)
        #     and reused by its parent — this is memoization via recursion,
        #     no need for an explicit memo table since the tree structure
        #     itself guarantees each subproblem is visited once
        #   - maxSum is NOT dp[root] — it's a separate global answer that
        #     checks, at every node, the path that uses BOTH branches
        #     (node as the "peak"), since dp[node] alone only tracks what
        #     can be extended upward

        # 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 maxKDivisibleComponents(self, n: int, edges: List[List[int]], values: List[int], k: int) -> int:

        # Greedy Tree Cutting:
        # The challenge is the problem asks for the MAXIMUM number of components,
        # so brute force would be to try every possible set of edge cuts
        # which would lead to O(2^n)

        # Greedy Tree Cutting avoids trying every combination and allows O(n),
        # as we can greedily cut edges bottom up using postorder DFS
 
        # Key Point:
        # When a subtree sum is divisible by k, we can safely cut it from its parent
        # because adding a multiple of k to any sum never changes its remainder

        # Summary:
        # Pass 1 (Postorder):
        #   - accumulate subtree sums bottom up
        #   - cut edge immediately when subtree sum % k == 0

        # Since the original graph is undirected,
        # we need a undirected adjacency list 
        # to represent the connection going both ways for each edge
        # sc: O(n)
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

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

        # ------------------------------
        # Pass 1: Postorder DFS (left- > right -> root)
        # Greedily cut edges bottom up, counting valid components

        # Need to calculate the components for children to determine components for root
        #   - 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)
        def dfs(node, parent):

            # Start subtree sum with current node's value
            subtree_sum = values[node]

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

                # Skip original parent to avoid cycles
                # (in case node is pointing to itself in adjacency list)
                if leftOrRight == parent:
                    continue

                subtree_sum += dfs(leftOrRight, 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 — proof above
                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

        # Pass 1: postorder greedy cut, count valid components
        dfs(0, -1)

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

    def checkEqualTree(self, root: Optional[TreeNode]) -> bool:
        
        # DFS Post Order Subtree Sum Target Match

        # Removing any single edge splits the tree into exactly two
        # pieces: the subtree rooted at the child side of that edge,
        # and everything else (totalSum minus that subtree's sum). For
        # those two pieces to have equal sums, the subtree's sum must
        # be exactly half of totalSum, which automatically guarantees
        # the remaining piece is the other half.

        # This means a valid partition exists if and only if some
        # subtree sum (other than the root's own sum, since there's no
        # edge above the root to remove) equals totalSum / 2.

        # We can compute every subtree's sum in a single post-order DFS
        # pass (children fully summed before the parent), collecting
        # each one as a candidate. The root's own final sum is excluded
        # afterward, since it represents "the whole tree," not a valid
        # split.

        # Edge Case:
        # a single node has no edges to remove at all
        if not root.left and not root.right:
            return False

        # Track every subtree sum encountered
        # sc: O(n)
        subtreeSums = []

        def dfs(node):

            # Base Case:
            # a null node contributes 0 to its parent's sum
            if not node:
                return 0

            # Process Children First (Post Order):
            # a node's subtree sum depends on both children's sums
            leftSum = dfs(node.left)
            rightSum = dfs(node.right)

            # Compute Subtree Sum:
            subtreeSum = node.val + leftSum + rightSum

            # Record Candidate Split:
            # removing the edge above this node produces this exact split
            subtreeSums.append(subtreeSum)

            return subtreeSum

        # Total sum of the entire tree, also the last value dfs() returns
        # tc: O(n)
        totalSum = dfs(root)

        # Exclude Root's Own Sum:
        # the whole tree's sum is not a valid split, there's no edge above it
        subtreeSums.pop()

        # Target Split Check:
        # a valid partition exists if some subtree equals exactly half
        # of totalSum, since the remaining piece automatically matches
        # tc: O(n)
        if totalSum % 2 != 0:
            return False

        target = totalSum // 2

        # overall: tc O(n), one DFS pass to compute all subtree sums,
        #   one linear pass to check for the target
        # overall: sc O(n), for subtreeSums plus O(h) recursion stack
        #   depth, h = height of tree
        return target in subtreeSums

    def maxProduct(self, root: Optional[TreeNode]) -> int:
        
        # DFS Post Order Subtree Sum Enumeration

        # Removing any single edge splits the tree into exactly two
        # pieces: the subtree rooted at the child side of that edge,
        # and everything else (the rest of the tree). If a subtree
        # rooted at some node has sum t, then removing the edge above
        # that node always produces a split of (t, totalSum - t).

        # This means every possible split is fully determined by every
        # possible subtree sum in the tree. Rather than simulating each
        # edge removal individually, we can compute every subtree's sum
        # in a single post-order DFS pass (children fully summed before
        # the parent), collecting each one as a candidate split point.

        # Once every subtree sum is known, the answer is just the
        # maximum of t * (totalSum - t) across all collected sums.

        MOD = 10**9 + 7

        # Track every subtree sum encountered
        # sc: O(n)
        subtreeSums = []

        def dfs(node):

            # Base Case:
            # a null node contributes 0 to its parent's sum
            if not node:
                return 0

            # Process Children First (Post Order):
            # a node's subtree sum depends on both children's sums
            leftSum = dfs(node.left)
            rightSum = dfs(node.right)

            # Compute Subtree Sum:
            subtreeSum = node.val + leftSum + rightSum

            # Record Candidate Split:
            # removing the edge above this node produces this exact split
            subtreeSums.append(subtreeSum)

            return subtreeSum

        # Total sum of the entire tree, also the last value dfs() returns
        # tc: O(n)
        totalSum = dfs(root)

        # Maximize Product Across All Candidate Splits:
        # for each subtree sum t, the split is (t, totalSum - t)
        # tc: O(n)
        maxProduct = 0
        for t in subtreeSums:
            maxProduct = max(maxProduct, t * (totalSum - t))

        # overall: tc O(n), one DFS pass to compute all subtree sums,
        #   one linear pass to find the best split
        # overall: sc O(n), for subtreeSums plus O(h) recursion stack
        #   depth, h = height of tree
        res = maxProduct % MOD

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

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

        # Re-rooting DP (Dynamic Programming On Trees):
        # The challenge is the problem asks for answer at EVERY node,
        # pretending as if that node is the root, so brute force would be:
        #   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),
        # as we can 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 we need to know the size of subtrees to calculate
        # how many nodes are closer and how many are now farther

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

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

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

        # Since the original graph is undirected,
        # we need a undirected adjacency list 
        # to represent the connection going both ways for each edge
        # sc: O(n)
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)


        # Sum of distances from node i to all other nodes:
        #   Ex: After our Post Order iteration for node 0, we get
        #       nodeToAllTotal[0] = sum of distances from root node 0 to all other nodes
        # sc: O(n)
        nodeToAllTotal = [0] * n


        # Subtree sizes for the subtree at each node:
        #   Re-rooting requires us to know the subtree sizes so
        #   we can modify the solution for node 0 for all other nodes
        #   while iterating from parent -> child, we must know:
        #       - how many nodes get closer?
        #       - how many nodes get farther?

        # Ex:
        #        0
        #       / \
        #      1   2
        #         / \
        #        3   4
        #
        # count[0] = 5  (entire tree)
        # count[1] = 1  (nodes 1)
        # count[2] = 3  (nodes 2,3,4)
        # count[i] = size of i's subtree

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


        # ------------------------------
        # Pass 1: Postorder DFS (left -> right -> root)
        #   - Solving for node 0 as the root, 
        #     find the total sum of distances to all nodes
        #   - Calculate the subtree size for the subtree at each node during iteration
        #     to be used during Preorder dfs

        # Process all children first:
        #   - pass up total distance needed
        #   - pass up subtree sizes
        def dfs_postOrder(node, parent):

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

                # Skip original parent to avoid cycles
                # (in case node is pointing to itself in adjacency matrix)
                if leftOrRight == parent:
                    continue

                # ----------------------------------
                # Generate subtree size for children

                # Process child subtree first,
                # and add children subtree size to parent
                dfs_postOrder(leftOrRight, node)
                subtreeSize[node] += subtreeSize[leftOrRight]


                # ----------------------------------
                # Use subtree size for children to calculate total distance for parent

                # distances from parent node to all nodes in parent's own subtree subtree =
                #   nodeToAllTotal[child]  — distances from child node to all nodes in child's own subtree
                #   + subtreeSize[child]   — every node in child's subtree is 1 edge farther from parent node than from child node
                nodeToAllTotal[node] += nodeToAllTotal[leftOrRight] + subtreeSize[leftOrRight]


        # ------------------------------
        # Pass 2: Preorder DFS (root -> left -> right)
        # Using the answer for node 0, derive the answer for all other nodes

        # We have solved for root already via DP (node 0 -> ith):
        #   - continue to solve downwards
        #   - propagate distances and re-root downward to children
        def dfs_preOrder(node, parent):

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

                # Skip original parent to avoid cycles
                # (in case node is pointing to itself in adjacency matrix)
                if leftOrRight == parent:
                    continue

                # ----------------------------------
                # Use parent's allNodeDistance to derive child's allNodeDistance

                # distances from child node to all nodes in child's own subtree =
                #   nodeToAllTotal[node]             — parent's distance to all nodes in tree
                #   - subtreeSize[leftOrRight]       — every node in child's subtree is 1 edge closer to child than to parent
                #   + (n - subtreeSize[leftOrRight]) — every node outside child's subtree is 1 edge farther from child than from parent
                nodeToAllTotal[leftOrRight] = nodeToAllTotal[node] - subtreeSize[leftOrRight] + (n - subtreeSize[leftOrRight])

                # ----------------------------------
                # Continue to propagate parent to children allNodeDistance

                # 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 construct(self, grid: List[List[int]]) -> 'Node':

        # DFS Post Order Quad Tree Construction:
        # (top-left -> top-right -> bottom-left -> bottom-right -> root)

        #   - Divide the grid into 4 equal sub-grids
        #   - Process all 4 children first (Post Order), then merge at root
        #   - If all 4 children are leaves with the same value (uniformity):
        #       the root collapses into a single leaf
        #   - If the 4 children don't uniformly match: 
        #       keep an internal node with all 4 children attached

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

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

            # Base Case 1x1 Grid:
            # We've reached a single 1x1 cell grid, 
            # which will always be a leaf since a single cell is by definition uniform.
            # Go back up recursion call to 4x4 cell grid and continue up
            if size == 1:
                return Node(val=bool(grid[r0][c0]), isLeaf=True)

            # 4x4 Cell Grid:
            # We have at least 4 cells,
            # now we need to validate if we have uniform cells or if we need to recurse
            
            # Divide:
            # split the current grid into 4 equal quadrants
            half = size // 2

            # Process Children First (Post Order):
            # recursively build each quadrant before merging at this level
            # tc: O(1) for each call, 
            # tc: O(n^2) recursive cost of the 4 children across recursion tree
            topLeft     = dfs(r0,        c0,        half)
            topRight    = dfs(r0,        c0 + half, half)
            bottomLeft  = dfs(r0 + half, c0,        half)
            bottomRight = dfs(r0 + half, c0 + half, half)

            # Merge Check:
            # root can collapse into a single leaf if:
            #   - all 4 children are leaves
            #   - all 4 leaves hold the same value
            subtreeLeaves = (  
                                topLeft.isLeaf and 
                                topRight.isLeaf and
                                bottomLeft.isLeaf and 
                                bottomRight.isLeaf
                            )
            subtreeValues = (
                                topLeft.val == 
                                topRight.val ==
                                bottomLeft.val == 
                                bottomRight.val
                            )

            # Grid Uniformity:
            # We can collapse into one leaf node
            if subtreeLeaves and subtreeValues:
                return Node(val=topLeft.val, isLeaf=True)

            # Grid Mismatch:
            # Create an internal node with 4 subtrees representing the 4 sub grids
            return Node(
                val=True, isLeaf=False,
                topLeft=topLeft,
                topRight=topRight,
                bottomLeft=bottomLeft,
                bottomRight=bottomRight
            )

        # Initialize at coordinates (0, 0)
        # tc: O(n^2) every cell is visited exactly once at the base case for the value uniformity check O(n^2)
        # sc: O(n^2 + log n) log n for the recursion stack itself + n^2 for the output quad tree
        quadTreeRoot = dfs(0, 0, n)

        # overall: tc O(n^2)
        # overall: sc O(log n)
        return quadTreeRoot