Invert Binary Tree

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree. Turn it into its mirror image: for every node, its left and right subtrees trade places. Return the root of the resulting tree.

After the change, reading any level of the tree from left to right gives the values of that level in the original tree from right to left.

Trees are written in level order: the root first, then each level from left to right, with null marking a missing child. For example [4,2,null,1] is a root 4 whose left child 2 has a left child 1.

Example 1

Input: root = [6,2,9,1,4,7,11] Output: [6,9,2,11,7,4,1] Why: Every node swaps its children, so each level appears reversed.

Example 2

Input: root = [3,1] Output: [3,null,1] Why: The single child moves from the left side to the right side.

Example 3

Input: root = [] Output: [] Why: An empty tree stays empty.

Constraints

0 <= number of nodes <= 1000
-1000 <= Node.val <= 1000
The depth of the tree is at most 100.

Pattern Path · Trees: DFS · problem 80 of 169

Suppose you could already mirror any smaller tree. How would you mirror a tree from its root?

Mirroring a tree means mirroring both subtrees and then putting them on opposite sides.

Swap the left and right child of the current node, then repeat the same process on each child (recursively, or with a queue or stack).

Target: O(n) time, O(h) extra space.

Start simple

Serialise each level, reverse it and rebuild a new tree from the reversed levels: still O(n) time, but O(n) extra memory and much more code than swapping in place.

The key idea

The mirror of a tree has a neat recursive description: the mirrored tree has the same root, its left subtree is the mirror of the original right subtree, and its right subtree is the mirror of the original left subtree. An empty tree is its own mirror, which is the base case.

That definition translates directly into code: mirror both children, then assign them to the opposite sides of the node. Because the work at each node is a constant-time swap and every node is visited once, the whole tree is mirrored in linear time, and it is done in place without creating new nodes.

The order does not matter: you can swap first and recurse afterwards, or traverse level by level with a queue and swap each node's children as you pop it. Every node just needs to be visited once. The recursive version uses stack space proportional to the height of the tree.

Complexity

Time: O(n)
Space: O(h)

Python

class Solution:
    def invertTree(self, root):
        if root is None:
            return None
        # Mirror both subtrees, then put each one on the opposite side.
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

JavaScript

var invertTree = function(root) {
  if (root === null) return null;
  // Mirror both subtrees, then put each one on the opposite side.
  const left = invertTree(root.left);
  root.left = invertTree(root.right);
  root.right = left;
  return root;
};

What the interviewer is checking

This is a quick check that you can think recursively about trees, state a base case, and visit every node exactly once, or do the same iteratively with a queue.

Mistakes to avoid

Swapping only the root's children and forgetting to mirror the subtrees below them.
Assigning root.left = invert(root.right) and then root.right = invert(root.left) in two steps, which reads the already-overwritten left child.
Forgetting the empty-tree case and dereferencing a null root.

Follow-ups to expect

Can you do it without recursion? (BFS with a queue, swapping each node.)
How would you check whether a tree is symmetric? (Compare it against its own mirror.)
How would you check if two trees are mirrors of each other? (Recursive left-right cross comparison.)

In real software

Mirroring hierarchical layouts, such as flipping a UI component tree or an org chart for right-to-left languages, applies the same swap at every node.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        return root;
    }
}

public class Main {
    // Builds a tree from a level-order array where null marks a missing child.
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

// Level-order list of the tree with nulls for missing children (trailing nulls removed).
    static List<Integer> levelOrder(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode n = q.poll();
            out.add(n == null ? null : n.val);
            if (n != null) { q.add(n.left); q.add(n.right); }
        }
        while (!out.isEmpty() && out.get(out.size() - 1) == null) out.remove(out.size() - 1);
        return out;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{6, 2, 9, 1, 4, 7, 11});
        System.out.println(levelOrder(new Solution().invertTree(root))); // [6, 9, 2, 11, 7, 4, 1]
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        return root;
    }
};

// Builds a tree from a level-order list where NIL marks a missing child.
const int NIL = INT_MIN;
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NIL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i] != NIL) { n->left = new TreeNode(a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i] != NIL) { n->right = new TreeNode(a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

int main() {
    TreeNode* root = Solution().invertTree(build({6, 2, 9, 1, 4, 7, 11}));
    // Print level order (null for missing children).
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* n = q.front(); q.pop();
        if (!n) { cout << "null "; continue; }
        cout << n->val << ' ';
        q.push(n->left);
        q.push(n->right);
    }
    cout << endl;  // 6 9 2 11 7 4 1 null null ... (trailing nulls)
}

Topics #080 #t-tree-dfs BFS DFS Easy Practice Tree