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

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

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

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

        # recursive call at root
        dfsPreOrder(root)

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

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

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

        # Empty Check
        if not root:
            return "N"

        # iteration via stack
        stack = [root]

        # serialized array
        vals = []
        
        while stack:

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

            # process root ->: if value
            if currRoot:

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

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


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

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

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

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

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

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

        # iteration via stack
        stack = [] 

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

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

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

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

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

        def dfs(node):
            nonlocal diameter

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

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

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

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

        # recursive on root
        dfs(root)

        # return global diameter
        return diameter

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

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

        # Empty check
        if not root:
            return 0

        # global width
        diameter = 0

        # iterative stack
        stack = []

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

        while stack or curr:

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

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

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

            # process node
            else:
                stack.pop()

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

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

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

                # set last visited to current node
                lastVisited = peek

        # return width
        return diameter

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

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

        group = []

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

        while queue:

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

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

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

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

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

        # return all level groups
        return groups

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

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

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

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

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

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

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

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

        # iteration stack
        queue = deque([root])

        # order toggle
        left_to_right = True
        
        while queue:

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

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

        return groups

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

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

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

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

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

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

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

    def 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # 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 invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: invert children nodes
        #   2. Process right node: invert children nodes
        #   3. Process root node: invert left and right nodes

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

        # Recursive call to process left subtrees
        left_inverted = self.invertTree(root.left)

        # Recursive call to process right subtrees
        right_inverted = self.invertTree(root.right)

        # Could have also been: right -> left subtrees
        # right_inverted = self.invertTree(root.right)
        # left_inverted = self.invertTree(root.left)

        # Process Root: 
        # Invert left and right nodes
        root.left = right_inverted
        root.right = left_inverted

        # Return invert to previous recursive call

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

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # 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 invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: invert children nodes
        #   2. Process right node: invert children nodes
        #   3. Process root node: invert left and right nodes

        # Empty Case: tree is a leaf, no swap, return None
        if not root:
            return None

        # Stack to hold:
        stack = []

        # Starting Iteration:
        curr = root

        # Tracking Last Visited:
        lastVisited = None 

        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while stack or curr:

            # Process Left Node: 
            # iterate as far down the left subtree line as we can,
            # by as many left subtree nodes to stack as we can
            while curr: 
                # push root node to stack
                stack.append(curr)
                # iterate to left node
                curr = curr.left

            # Implies: reached the last node on the left subtree line

            # Grab: root node we just placed on stack (root of last left subtree)
            peek = stack[-1]

            # Check: if root node of the last left subtree has a right subtree
            # Check: if right subtree has not been visited
            # Then: iterate to right subtree and in next while loop, 
            #       the left subtree of the right subtree will be explored fully
            if peek.right and lastVisited != peek.right:
                curr = peek.right
            
            # Implies: no right subtree exists
            # Implies: finished processing left and right subtree
            # Then: process root 
            else:
                # Remove And Process: pop root node from stack
                stack.pop()

                # Process Root Node:
                # Invert left and right nodes
                peek.left, peek.right = peek.right, peek.left

                # Mark Root Node:
                # Set last visited to current to avoid revisiting
                lastVisited = peek

        # tc: 
        # sc:
        return root

    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # 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 invert a tree, we simply have to swap 
        # the L and R children nodes at each node:
        #       1
        #      / \
        #     3   2
        #    / \
        #   4   5

        # BFS Iterative Level By Level: 
        # Process root level -> process left and right level
        #   1. Process Root: iterate over roots level
        #        - swap left and right subtrees
        #   2. Process Left And Right: append left and right nodes to process them
        #        - left and right will be process along with all nodes in their level
        
        # Empty Case: tree is a leaf, no swap, return None
        if not root:
            return None
        
        # Iterative level stack:
        queue = deque([root])
        
        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while queue:

            # Number Of Nodes In Current Level Of Tree:
            size = len(queue)

            # Process The full Level Before Iterating To Next Level:
            for _ in range(size):

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

    def maxDepth(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 height of a tree, we simply have to compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found, while adding +1
        # to account for the current root node

        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: get height of tree
        #   2. Process right node: get height of tree
        #   3. Process root node: compare max height between left and right, add +1
        
        # Empty Case: tree is a leaf, no height, return 0
        if not root:
            return 0
        
        # Recursive call to process left subtrees
        left_depth = self.maxDepth(root.left)

        # Recursive call to process right subtrees
        right_depth = self.maxDepth(root.right)
        
        # Could have also been: right -> left subtrees
        # right_depth = self.maxDepth(root.right)
        # left_depth = self.maxDepth(root.left)

        # Process Root:
        # compare max height between left and right, add 1
        root_depth = 1 + max(left_depth, right_depth)

        # Return max height of tree

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

    def maxDepth(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 height of a tree, we simply have to swap compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found
        
        # DFS PostOrder: 
        # left -> right -> root
        #   1. Process left node: get height of tree
        #   2. Process right node: get height of tree
        #   3. Process root node: compare max height between left and right
        
        # Empty Case: tree is a leaf, no height, return = 0
        if not root:
            return 0

        # Stack to hold:
        stack = []

        # Starting Iteration:
        curr = root

        # Tracking Last Visited:
        lastVisited = None

        # Iterative Height Map Tracking:
        # Since we are using a stack, we will not have access to
        # the children left and right at the same time, so we need to
        # keep track of the heights in the hashmap
        heightMap = defaultdict(int)

        # Check: of we still have nodes to process
        # tc: iterate over n O(n)
        while stack or curr:
            
            # Process Left Node: 
            # iterate as far down the left subtree line as we can,
            # by as many left subtree nodes to stack as we can
            while curr:
                # push root node to stack
                stack.append(curr)
                # iterate to left node
                curr = curr.left
            
            # Implies: reached the last node on the left subtree line

            # Grab: root node we just placed on stack (root of last left subtree)
            peek = stack[-1]

            # Check: if root node of the last left subtree has a right subtree
            # Check: if right subtree has not been visited
            # Then: iterate to right subtree and in next while loop, 
            #       the left subtree of the right subtree will be explored fully
            if peek.right and lastVisited != peek.right:
                curr = peek.right

            # Implies: no right subtree exists
            # Implies: finished processing left and right subtree
            # Then: process root 
            else:
                # Remove And Process: pop root node from stack
                stack.pop()
                
                # Grab left and right height result from hashmap 
                left_depth = heightMap[peek.left]
                right_depth = heightMap[peek.right]

                # Process Root Node:
                # compare max height between left and right, add 1
                currentDepth = 1 + max(left_depth, right_depth)

                # Track Root Node:
                # Add this nodes height to the dictionary
                heightMap[peek] = currentDepth

                # Mark Root Node:
                # Set last visited to current to avoid revisiting
                lastVisited = peek

        # final height of tree
        heightOfTree = heightMap[root]

        # overall: tc 
        # overall: sc 
        return heightOfTree

    def maxDepth(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 height of a tree, we simply have to swap compare
        # the max height of each subtree at each root node, 
        # and keep track of the max height found

        # BFS Iterative Level By Level: 
        # Process root level -> process left and right level
        #   1. Process Root: iterate over roots level 
        #       - no action needed, when finished iteration over nodes in 
        #         level, added 1 to global depth counter
        #   2. Process Left And Right: append left and right nodes to process them
        #        - left and right will be process along with all nodes in their level
        
        # Empty Case: tree is a leaf, no height, return = 0
        if not root:
            return 0
        
        # Iterative level stack:
        stack = [(root, 1)]

        # Global depth
        globalDepth = 0
        
        # Check: if we still have nodes to process
        # tc: iterate over n O(n)
        while queue:

            # Number Of Nodes In Current Level Of Tree:
            size = len(queue)

            # Process The full Level Before Iterating To Next Level:
            for _ in range(size):

                # Remove And Process:
                # no action needed on root node
                node = queue.popleft()

                # Prepare Next Level:
                # Append the next level of nodes to the stack,
                # will not affect the current level processing 
                # as we have previously determined the number of nodes in the level 
                # and thus the number of nodes to be process
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # level complete, add +1 to depth counter to account for this level
            globalDepth += 1
        
        # overall: tc O(n)
        # overall: sc O(n)
        return globalDepth

    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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Process root -> :
        #    if both nodes are 'None' -> trees match
        #    if only one node is 'None' -> trees differ
        #    if values mismatch -> trees differ
        # 3. Process -> left -> right :
        # Result: validate tree match 
        
        # Note: this is 'process root' instead of 'base case'
        # because it leads to an early termination, instead of being a regular base case
        # thus, this solution is pre order

        # Process root -> : both nodes are 'None'
        if not p and not q:
            return True

        # Process root -> : only one node is 'None' 
        if not p or not q:
            return False

        # Process root -> : values differ
        if p.val != q.val:
            return False
        
        # Process left -> right
        left_match = self.isSameTree(p.left, q.left)
        right_match = self.isSameTree(p.right, q.right)

        # Process left -> right : pass left and right results up
        subTreeMatch = left_match and right_match
        
        # overall: time complexity
        # overall: space complexity
        return subTreeMatch

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Note:
        # BFS Iterate: level by level
        # 1. Process root -> : 
        #    if both nodes are 'None' -> trees match
        #    if only one node is 'None' -> trees differ
        #    if values mismatch -> trees differ
        # 2. Process -> left -> right : 
        # Result: validate tree match 
        
        # iterative stack
        queue = deque([(p, q)])
        
        while queue:

            # process root -> :
            root1, root2 = queue.popleft()
            
            # Note: early termination during process root -> : 

            # Process root -> : both nodes are 'None'
            if not root1 and not root2:
                continue
            
            # Process root -> : only one node is 'None' 
            if not root1 or not root2
                return False
            
            # Process root -> : values differ
            if root1.val != root2.val:
                return False
            
            # process -> left -> right
            queue.append((root1.left, root2.left))
            queue.append((root1.right, root2.right))
        
        # overall: time complexity
        # overall: space complexity
        return True

    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 lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node
        
        # process root -> :
        # p and q are smaller, LCA in left subtree 
        if p.val < root.val and q.val < root.val:

            # process -> left :
            return self.lowestCommonAncestor(root.left, p, q)

        # process root -> :
        # p and q are larger, LCA in right subtree
        elif p.val > root.val and q.val > root.val:

            # process -> right :
            return self.lowestCommonAncestor(root.right, p, q)
        
        # process root -> :
        # p and q are in different subtrees, root is LCA
        else:
            return root

        # overall: time complexity
        # overall: space complexity

    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        # Note:
        # BST traversal: root -> either -> left or -> right
        # 1. Process -> root : 
        #    determine if LCA is in left or right
        # 2. Process -> left or -> right :
        # Result: find LCA node

        # iterative root
        while root:

            # process root -> :
            # p and q are smaller, LCA in left subtree 
            if p.val < root.val and q.val < root.val:

                # process -> left :
                root = root.left

            # process root ->
            # p and q are larger, LCA in right subtree
            elif p.val > curr.val and q.val > curr.val:

                # process -> right :
                curr = curr.right

            # process root -> :
            # p and q are in different subtrees, root is LCA
            else:
                return curr
        
        # overall: time complexity
        # overall: space complexity

    def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        
                
        # Binary Search Tree:
        # BST property: For any node:
        #    left subtree nodes < node.val < right subtree nodes
        #
        # Example:
        #        4
        #       / \
        #      2   7
        #     / \
        #    1   3
        #
        # Inserting val = 5:
        #        4
        #       / \
        #      2   7
        #     / \  /
        #    1   3 5

        # Recursive DFS:
        #   1. Compare val with root.val
        #   2. If val < root.val, recurse left
        #   3. If val > root.val, recurse right
        #   4. If reached None, insert node here
        
        # Base case: reached a leaf, insert new node here
        if not root:
            # tc O(1), sc O(1) for node creation
            return TreeNode(val)
        
        # Decide whether to insert left or right
        if val < root.val:
            # Insert into left subtree
            root.left = self.insertIntoBST(root.left, val)
        else:
            # Insert into right subtree
            root.right = self.insertIntoBST(root.right, val)
        
        # Return root node to maintain BST structure upwards
        # tc: O(h) for traversing height of tree
        # sc: O(h) recursion stack (O(log n) balanced, O(n) skewed)
        return root