Invert Binary Tree

The problem

You are given the root of a binary tree. A binary tree is a set of nodes where each node has at most two children: a left one and a right one.

Turn the tree into its mirror image. Every left child becomes a right child, and every right child becomes a left child, at every level. Return the root of the changed tree.

Trees in the examples are written level by level, from left to right. null marks a missing child.

Example 1

Input: root = [5, 3, 8, 1, 4, 7, 9]

Output: [5, 8, 3, 9, 7, 4, 1]

Hold the tree up to a mirror. 8 and 3 change sides under 5. Inside each of them, the two children change sides too.

Example 2

Input: root = [2, 1]

Output: [2, null, 1]

2 has only a left child. In the mirror, 1 becomes the right child.

Example 3

Input: root = []

Output: []

An empty tree has nothing to swap.

Constraints

• The tree has n nodes, where 0 ≤ n ≤ 100.
• -100 ≤ Node.val ≤ 100

Clarifying questions

Can the tree be empty?

Yes. Then we return the empty tree (null) as it is.

Should we change the tree or build a new one?

Changing it in place is fine. We return the same root.

Do the values matter?

No. We only move nodes around. No value is read or compared.

Can the tree be very deep?

At most 100 nodes, so at most 100 levels. Recursion that deep is safe in every language.

Spot the pattern

The mirror of a tree is made of the mirrors of its two subtrees, swapped. That is the same job on a smaller tree. When a tree problem splits into “do the same thing to each child”, it is a tree traversal with recursion: visit every node once and do a small job there.

Solutions

RecursionO(n)

Show all

There is only one approach worth showing. Every node must move, so no method can visit fewer than n nodes, and this one visits each node once.

Recursion O(n)

The idea

Look at one node. To mirror the tree under it, two things must happen. Its two children must change sides. And each child’s own subtree must be mirrored inside.

So the function does exactly that. It swaps the two children of the node. Then it calls itself on each child. A call on an empty child stops at once. That is the base case, the point where the recursion stops.

The order does not matter. Swapping first and recursing second works, and so does the other way round.

Why it is correct: every node is visited exactly once, and at that visit its two children change sides. A tree in which every node has swapped its children is exactly the mirror.

Walkthrough

call stack top →

empty

1. def invert(node):
2. if node is None:
3. return None
4. node.left, node.right = node.right, node.left
5. invert(node.left)
6. invert(node.right)
7. return node

To mirror the tree, every node must swap its left and right child. Start the recursion at the root, 5.

← BackStep →Play1 / 18

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Recursion: swap the two children of a node, then fix each subtree
    // the same way. Every node is visited once, so n steps.
    public TreeNode invertTree(TreeNode root) {
        // An empty tree is already its own mirror.
        if (root == null) return null;
        // Swapping the children mirrors this level.
        TreeNode oldLeft = root.left;
        root.left = root.right;
        root.right = oldLeft;
        // Each subtree must be mirrored inside too.
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

Big O

Time O(n)Space O(h)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There is no loop here. The work repeats through recursion: the function calls itself. So we count the calls. Each call does a fixed job: one check for empty, one swap and two calls. That job does not grow with the tree, so each call counts as 1 step.

   1. def invert(node):
   2. if node is None:
   3. return None
   4. node.left, node.right = node.right, node.left
   5. invert(node.left)
   6. invert(node.right)
   7. return node

2. 2 Count the runs on Example 1

   Example 1 has 7 nodes. Each node gets exactly one call. The 4 leaves (1, 4, 7, 9) each have 2 empty children, and each empty child gets a call too. That call checks for empty and returns.

   7 node calls + 8 empty calls = 15 calls.

   total calls

   7 nodes + 8 empty children = 15

3. 3 Write the count for any n

   Every node gets one call. A binary tree with n nodes always has n + 1 empty child spots, and each of those gets one call too.

   n + (n + 1) = 2n + 1 calls

   Check it with Example 1: 2 × 7 + 1 = 15.

4. 4 Keep only the part that grows fastest

   • Drop the + 1. One call more does not change how the work grows.
   • Drop the 2. Doubling every count does not change the growth either. When n doubles, 2n doubles too.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code makes no list or map. But each call waits on the call stack until its children finish. The call stack is the memory a program keeps for calls that have started and not yet returned. Its deepest point is the height of the tree, written h: the number of levels on the longest path down.

   In Example 1, h is 3, so at most 3 calls wait at once (for example 5, 8 and 9). A balanced tree has h about log n. A tree shaped like a single chain has h = n. So the space is O(h), which is O(n) in the worst case.

   call stack (one frame per level)

Common mistake

Overwriting a child before saving it

Writing node.left = node.right and then node.right = node.left loses the old left child. Both sides end up as the same subtree. Swap with a temporary variable, or with one tuple assignment.

Tested at the limits

2,000 random trees of 0 to 12 nodes, in every shape, with repeated values. The recursion gave the same tree every time as a simple check that swaps the children level by level.

Largest inputs	Result
100 nodes (the most allowed), balanced. Recursion.	Under 0.001 s, and under 0.01 MB of extra memory: only a few calls wait at once.
100 nodes in one long line. Recursion.	Under 0.001 s, and about 0.01 MB of extra memory: 100 calls wait at once, one per level, which is the O(h) space.