Problem Description

You are given the root of a binary tree. Your task is to invert the tree and return its root.

Inverting a binary tree means swapping the left and right children of every node in the tree. This operation should be performed recursively throughout the entire tree structure.

For example, if you have a tree where a node has a left child L and a right child R, after inversion, that same node would have R as its left child and L as its right child. This swapping process applies to every single node in the tree, transforming the original tree into its mirror image.

The solution uses a recursive approach that:

1. Checks if the current node (root) is None - if so, returns None
2. Recursively inverts the left subtree and stores it in variable l
3. Recursively inverts the right subtree and stores it in variable r
4. Swaps the children by assigning the inverted right subtree (r) to root.left and the inverted left subtree (l) to root.right
5. Returns the current root node with its children now swapped

This bottom-up recursion ensures that all subtrees are inverted before their parent nodes, resulting in a completely inverted binary tree.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Yes: Since we identified this as a tree problem, the flowchart leads us to DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for inverting the binary tree.

This makes perfect sense because:

1. We need to visit every node in the tree to perform the inversion
2. DFS allows us to recursively traverse to the leaf nodes first, then work our way back up
3. The recursive nature of DFS aligns perfectly with the recursive structure of trees
4. We can invert subtrees bottom-up: first invert the left and right subtrees, then swap them at the current node

The solution implements DFS through recursion - it traverses down to the leaf nodes, inverts them (base case returns None for null nodes), and then swaps the left and right children as it returns back up the call stack. This is a classic application of the DFS pattern on a tree structure.

Intuition

When we think about inverting a binary tree, we're essentially creating a mirror image of the original tree. Imagine looking at a tree in a mirror - everything on the left appears on the right, and vice versa.

The key insight is that this mirroring operation needs to happen at every level of the tree. Each node's left and right children need to be swapped. But here's the crucial part: before we swap a node's children, those children themselves (which are subtrees) also need to be inverted first.

This naturally leads us to think recursively: to invert a tree rooted at a node, we first need to invert its left subtree and its right subtree independently, then swap these already-inverted subtrees.

Why does this work? Consider the recursive structure:

• If we have a leaf node (no children), there's nothing to invert
• If we have None (empty tree), we return None
• For any other node, we break down the problem into smaller subproblems: invert the left subtree, invert the right subtree, then swap them

The beauty of this approach is that by the time we swap the children at any node, we've already ensured that those children (and all their descendants) have been properly inverted. This bottom-up approach guarantees that the entire tree gets inverted correctly.

Think of it like renovating a building floor by floor from bottom to top - you complete each floor before moving to the next one. Similarly, we complete the inversion of smaller subtrees before handling their parent nodes, eventually inverting the entire tree when we reach the root.

Solution Approach

The solution implements a recursive DFS approach to invert the binary tree. Let's walk through the implementation step by step:

Base Case: The first check if root is None: return None handles the base case. When we encounter a null node (empty subtree), we simply return None. This stops the recursion and handles leaf nodes' null children.

Recursive Calls:

l, r = self.invertTree(root.left), self.invertTree(root.right)

This line makes two recursive calls:

• self.invertTree(root.left) recursively inverts the entire left subtree and stores the result in l
• self.invertTree(root.right) recursively inverts the entire right subtree and stores the result in r

The key insight here is that these recursive calls will completely invert their respective subtrees before returning. By the time we get the values of l and r, they represent fully inverted subtrees.

The Swap:

root.left, root.right = r, l

This is where the actual inversion happens at the current node level. We assign:

• The inverted right subtree (r) to become the new left child
• The inverted left subtree (l) to become the new right child

This Python syntax performs a simultaneous assignment, elegantly swapping the children in one line.

Return the Root: Finally, return root returns the current node with its children now swapped. As the recursion unwinds back up the tree, each level performs this swap, ultimately returning the root of the completely inverted tree.

The algorithm visits each node exactly once, making it an O(n) time complexity solution where n is the number of nodes. The space complexity is O(h) where h is the height of the tree, due to the recursive call stack.

Example Walkthrough

Let's walk through inverting a small binary tree step by step to illustrate the solution approach.

Initial Tree:

       4
      / \
     2   7
    / \   \
   1   3   9

Step 1: Start at root (4)

• We call invertTree(4)
• Node 4 is not None, so we proceed to recursive calls
• We call invertTree(2) for the left subtree and invertTree(7) for the right subtree

Step 2: Process left subtree rooted at 2

• In invertTree(2):
  • Node 2 is not None
  • Call invertTree(1) for left child and invertTree(3) for right child

Step 3: Process leaf nodes 1 and 3

• invertTree(1):
  • Node 1 is not None
  • Call invertTree(None) for both children → returns None for both
  • Swap: 1.left = None, 1.right = None (no change since both are None)
  • Return node 1
• invertTree(3):
  • Similar process, returns node 3

Step 4: Complete inversion of subtree rooted at 2

• Back in invertTree(2):
  • l = node 1 (inverted left subtree)
  • r = node 3 (inverted right subtree)
  • Swap: 2.left = 3, 2.right = 1
  • Return node 2 (now with children swapped)

Step 5: Process right subtree rooted at 7

• In invertTree(7):
  • Node 7 is not None
  • Call invertTree(None) for left child → returns None
  • Call invertTree(9) for right child
  • invertTree(9) processes and returns node 9 (leaf node)
  • Swap: 7.left = 9, 7.right = None
  • Return node 7 (now with children swapped)

Step 6: Complete inversion at root

• Back in invertTree(4):
  • l = inverted subtree rooted at 2 (which now has 3 on left, 1 on right)
  • r = inverted subtree rooted at 7 (which now has 9 on left, None on right)
  • Swap: 4.left = node 7, 4.right = node 2
  • Return node 4

Final Inverted Tree:

       4
      / \
     7   2
    /   / \
   9   3   1

The recursion ensures that each subtree is fully inverted before being swapped at its parent level, working from the bottom up to create the complete mirror image of the original tree.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm visits each node in the binary tree exactly once. At each node, it performs a constant amount of work (swapping the left and right child references). Since there are n nodes in the tree and each node is processed once, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity comes from the recursive call stack. In the worst case, when the tree is completely unbalanced (e.g., a skewed tree that resembles a linked list), the recursion depth can be O(n). In the best case of a balanced tree, the recursion depth would be O(log n). However, we consider the worst-case scenario for space complexity analysis, which gives us O(n).

Additionally, the algorithm stores temporary references l and r for the inverted subtrees, but these don't add to the overall space complexity as they are constant space operations at each recursive level.

Common Pitfalls

1. Attempting to Swap Before Recursive Calls

A common mistake is trying to swap the children before making the recursive calls:

Incorrect Implementation:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
  
    # WRONG: Swapping before recursion
    root.left, root.right = root.right, root.left
  
    self.invertTree(root.left)
    self.invertTree(root.right)
  
    return root

Why This Fails: While this might seem logical, it has a critical flaw. After swapping, when you call self.invertTree(root.left), you're actually processing what was originally the right subtree. The recursive calls don't return values that get assigned back to the children, so you lose the reference to the inverted subtrees.

Solution: Always store the results of recursive calls and then perform the swap:

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

2. Modifying References During Traversal

Another pitfall is trying to swap while simultaneously traversing:

Incorrect Implementation:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
  
    # WRONG: Directly assigning recursive results without temporary variables
    root.left = self.invertTree(root.right)
    root.right = self.invertTree(root.left)  # root.left has already been modified!
  
    return root

Why This Fails: After the first assignment root.left = self.invertTree(root.right), the original left subtree reference is lost. The second line then processes the already-modified root.left (which now contains the inverted right subtree), leading to incorrect results.

Solution: Store both recursive results before any assignments:

l, r = self.invertTree(root.left), self.invertTree(root.right)
root.left, root.right = r, l

3. Forgetting to Return the Root

Incorrect Implementation:

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None
  
    l, r = self.invertTree(root.left), self.invertTree(root.right)
    root.left, root.right = r, l
  
    # WRONG: Forgetting to return root

Why This Fails: Without returning root, the function returns None by default in Python, causing the entire tree structure to be lost as the recursion unwinds.

Solution: Always return the modified root node to maintain the tree structure:

return root