Here is solutions for Invert Binary Tree.

1. Understand the problem

Given the root of a binary tree, invert the tree.

• “Invert” means: for every node, swap its left and right children.

2. Clarify constraints, asks 4 - 5 questions including edge cases - Worst case of tree is a Linked List

1. Can the tree be empty?

• Yes. If root is None, just return None.

1. Is it guaranteed to be a binary tree?

• Yes, every node has at most 2 children: left and right.

1. Can the tree be unbalanced or skewed?

• Yes. Height can be up to n in the worst case (like a linked list).

1. What’s the maximum number of nodes?

• Typically up to 10^4 or 10^5 on LeetCode (we design for O(n) time, O(h) space).

1. Are node values unique? Does it matter?

• Values might not be unique, but we don’t care: we’re swapping pointers, not values.

3. Explore examples.

1. Example 1:

• Input:

       4
     /   \
    2     7
   / \   / \
  1   3 6   9

• Output:

       4
     /   \
    7     2
   / \   / \
  9   6 3   1

1. Example 2:

• Input:

    1
   /
  2
 /
3

• Output:

1
 \
  2
   \
    3

4. Brainstorm 2 - 3 solutions

4.1. Recursive DFS (Top-down) - Time O(N), Space O(H)

At each node:

1. Swap node.left and node.right.

2. Recursively invert the left subtree.

3. Recursively invert the right subtree.

4. Return node.

• Time: O(N).

• Space: O(H).

  • H = N for skew tree.
  • H = logN for balanced tree.

4.2. Solution 2: Iterative DFS using a stack - Time O(N), Space O(H)

Key idea:

1. Use a stack to simulate recursion:

   • Push root to stack.

2. While stack not empty:

   • Pop a node.

   • Swap its left and right child.

   • Push its (new) left and right children onto stack (if they’re not None).

• Time: O(n).

• Space: explicit stack, up to O(h) or O(n) in worst case.

         (Height = h)
              1
           /     \
          2       3
        /  \     /  \
       4    5   6    7
      / \  / \ / \  / \
     8 ...            15  <-- ~2^h nodes (~n/2)

• If n = 15 nodes, the last level could be 8 nodes => Space: O(N/2).

5. Implement solutions.

5.1. Breadth First Search - Time O(N), Space O(N/2) ~ O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return root

• Time: O(N).

• Space: O(N/2) ~ O(N)

5.2. Depth First Search - Time O(N), Space O(H) ~ Worst case O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

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

        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)

        return root

• Time: O(N).

• Space: O(H) ~ Worst case O(N).

5.3. Iterative DFS - Time O(N), Space O(H) ~ Worst case O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

• Time: O(N).

• Space: O(H) ~ Worst case O(N).

6. Dry run testcases.

• Dry run examples:

       4
     /   \
    2     7
   / \   / \
  1   3 6   9

• Idea: Similar idea to swap address of the nodes.