Invert Binary Tree: recursion as a natural fit

Trees are recursive structures. A tree is a node with a left subtree and a right subtree, and each of those subtrees is itself a tree. Once you internalise that, a problem like invert binary tree stops feeling like a problem. It reads as a specification: mirror this node, then mirror each child. The code is almost a transcription.

What the problem asks and what the constraints force

Given a tree rooted at root, swap every left child with its corresponding right child at every node, all the way down. Input [4,2,7,1,3,6,9] becomes [4,7,2,9,6,3,1]. The root stays; its subtrees swap; those subtrees' subtrees swap; and so on.

The constraint set is minimal: at most 100 nodes, values in [-100, 100]. Neither of those forces any cleverness. 100 nodes means O(n²) would be fine, O(n³) might even squeak through. There is no scale pressure here — the problem is entirely about seeing the structure.

What n <= 100 does tell you: call stack depth is at most 100 frames, so recursive DFS has no stack overflow risk. That's the one constraint with a practical consequence: the "use an iterative solution to avoid stack overflow" argument, valid for trees of depth 10,000, simply does not apply here. Choosing between recursive and iterative is a clarity question, not a correctness one.

The values [-100, 100] are irrelevant to the algorithm. The node values never influence the inversion; we only touch pointers.

The keywords that should fire off this pattern: "invert", "mirror", "flip", or "reverse" a tree. Any time you see symmetric or reflective operations on every node in a binary tree, you are looking at this exact shape.

Approach 1: Recursive DFS — O(n) time, O(h) space

The recursive solution has three lines of actual logic.

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;
        (root.left, root.right) = (root.right, root.left);
        InvertTree(root.left);
        InvertTree(root.right);
        return root;
    }
}

Base case: null node means nothing to invert — return immediately. Recursive case: swap the children, then recurse into each. Return root so the original pointer stays valid.

The order of operations matters slightly. You swap first, then recurse into what are now the swapped children. Either order produces a correct tree because you invert the whole subtree regardless — but swapping before recursing makes the mental model cleaner: this node is done, now go fix what it points to.

By-hand trace through the main example

Input: [4,2,7,1,3,6,9]

The call stack unwinds like this:

Call invertTree(4)

• Swap: root.left=2, root.right=7 -> after swap: root.left=7, root.right=2
• Push recursive call on 7 (now left child)

Call invertTree(7)

• Swap: root.left=6, root.right=9 -> after swap: root.left=9, root.right=6
• Push recursive call on 9

Call invertTree(9) - no children, return null on both sides, return 9

Call invertTree(6) - no children, return null on both sides, return 6

Back in invertTree(7): both children done, return 7

Call invertTree(2) (now right child of root)

• Swap: root.left=1, root.right=3 -> after swap: root.left=3, root.right=1
• Both children are leaves, recursion terminates immediately

Back in invertTree(4): both children fully inverted, return 4

Result:

Every node visited exactly once. Each visit is O(1). Total: O(n) time, O(h) space for the call stack where h is tree height. Worst case on a completely skewed tree is O(n). A balanced tree gives O(log n).

Why recursion is the natural fit

When you see a tree problem, ask: does the answer for this node depend on the answers from its children? If yes, recursion is almost always the right shape.

For invert: the inverted version of a node is that node with its children swapped, where each swapped child is itself already inverted. The definition is circular in exactly the way that recursion handles. You are not computing anything complicated at each node — you swap two pointers. Then you let the recursive calls handle the rest, trusting that they follow the same rule.

This is what people mean when they say recursion "reduces the problem to subproblems of the same shape." The subproblems here are literally the same problem on a smaller tree. The base case (null) terminates the chain.

In an interview I would write this version without hesitation. It is short, it is correct, and it communicates the structure of the algorithm directly.

Approach 2: Iterative BFS — O(n) time, O(w) space

If you want an iterative solution, BFS with a queue is the most natural. Process nodes level by level; at each node, swap children and enqueue them.

from collections import deque
 
class Solution:
    def invertTree(self, root: TreeNode) -> 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

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        while (queue.Count > 0) {
            var node = queue.Dequeue();
            (node.left, node.right) = (node.right, node.left);
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
        return root;
    }
}

Walking through the same example — level by level this time:

queue = [4]

Iteration 1: pop 4, swap children (2 <-> 7), enqueue [7, 2]
Iteration 2: pop 7, swap children (6 <-> 9), enqueue [2, 9, 6]
Iteration 3: pop 2, swap children (1 <-> 3), enqueue [9, 6, 3, 1]
Iterations 4-7: pop leaves 9, 6, 3, 1 — no children to enqueue
queue empty, done

The order in which you visit nodes is different from DFS — you process the tree level by level — but you still visit every node exactly once and perform one swap per node.

Complexity: O(n) time, same as the recursive version. O(w) space, where w is the maximum width of the tree (the widest level). For a perfectly balanced tree, that is O(n/2) = O(n) at the bottom level. For a completely skewed tree, it is O(1). In the average case, BFS uses more memory than DFS on this problem.

The BFS version avoids call stack depth, which is sometimes cited as a reason to prefer it. On a tree with 100 nodes and LeetCode constraints, stack overflow is not a practical concern. The iterative version is correct and clear, but I would not reach for it first on this problem.

Approach 3: Iterative DFS with an explicit stack — O(n) time, O(h) space

You can mirror the recursive DFS iteratively using an explicit stack. The logic is the same: pop a node, swap its children, push them.

class Solution:
    def invertTree(self, root: TreeNode) -> 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

public class Solution {
    public TreeNode InvertTree(TreeNode root) {
        if (root == null) return null;
        var stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count > 0) {
            var node = stack.Pop();
            (node.left, node.right) = (node.right, node.left);
            if (node.left != null) stack.Push(node.left);
            if (node.right != null) stack.Push(node.right);
        }
        return root;
    }
}

This produces a pre-order-ish traversal, but the traversal order does not affect correctness here. Every node gets swapped exactly once regardless of whether you visit it depth-first or breadth-first. The stack version and the queue version both work; they just visit nodes in different sequences.

Edge cases, and why the code handles them

Three cases worth naming explicitly:

Empty tree (root = null): the if not root / if (root == null) guard returns immediately in all three approaches. Nothing is ever enqueued or pushed. The caller gets null back, which is the correct empty-tree output.

Single node (no children): the swap executes (None, None = None, None in Python — a no-op), and both recursive calls immediately hit the base case. The node returns unchanged. BFS and stack variants enqueue nothing after the pop. Correct in all three.

Completely skewed tree (a chain of 100 nodes, each with only a left child): the recursion goes 100 frames deep. Stack depth is O(n) rather than O(log n). On this problem's constraints that is 100 frames — harmless. If the constraint were n = 100,000, this would be the argument for the iterative DFS; here it is not.

Nodes with only one child (e.g., left child present, right is null): the swap runs correctly — (node, null) becomes (null, node). The non-null child gets enqueued/pushed; the null side never does (guarded by if node.left / if node.right). Nothing breaks.

The classic mistake: writing root.left = root.right; root.right = root.left without a temp variable. The second line re-reads the already-overwritten root.left, so both sides end up pointing to the original right child. In Python, tuple unpacking (a, b = b, a) evaluates the right side before any assignment. In C#, the deconstruction syntax (a, b) = (b, a) does the same. In languages without either shorthand — Go, Java with manual swap — always use a temp variable.

Which one to write

Recursive. Every time, on this problem.

The recursion makes the structure of the solution visible. A reader can see immediately that the algorithm is: do this thing at the root, then do the same thing at each child. The iterative versions obscure that behind a loop and an auxiliary data structure. They are not wrong — but they are a worse description of what is actually happening.

The only argument for the iterative version is avoiding deep call stacks. On any tree you will encounter in an interview or on LeetCode, that is not a real concern. If someone raises it, you can acknowledge it and then point out that for this specific problem, on realistic inputs, the recursive version is strictly preferable in terms of readability.

Complexity across all three approaches

All three are O(n) time. The space differences are real but small in practice — and for most trees, O(h) and O(w) are within a constant factor of each other. The space asymmetry reverses depending on tree shape: BFS is better on a skewed tree, DFS is better on a perfectly balanced one.

Related problems

Maximum Depth of Binary Tree (104) is the next natural step in this series. It uses the same recursive skeleton: at each node, ask both children for their depth, take the max, add one. The pattern is "recurse into both children and combine the results" — invert uses the same structure but discards the return values of the recursive calls (we care only about side effects, not about aggregating a value).

Symmetric Tree (101) is the inverse question — not modifying the tree but checking whether it already looks like its own mirror image. The recursion compares left.left against right.right and left.right against right.left simultaneously. If the inversion recursive structure felt clear, the symmetry check will feel familiar — it is the same traversal shape, but read-only.

Binary Tree Level Order Traversal (102) is where BFS earns its place. Level-order traversal is a problem where the BFS queue is the natural fit because you need to group nodes by depth — something DFS cannot give you cleanly. After invert, it is worth seeing a problem where the iterative BFS is the right tool by necessity rather than by optional preference.

Same Tree (100) uses a similar recursive comparison structure. Pairing it with Symmetric Tree gives you back-to-back examples of comparing two trees (or a tree against itself) using DFS, which builds the pattern recognition for when DFS is the structurally correct choice.