Difficulty: Easy · LeetCode 226

Problem

Given the root of a binary tree, invert the tree, and return its root (swap left and right subtrees recursively).

Understanding the problem

Inverting a tree means swapping every left child with its corresponding right child at every node in the tree.

Intuition

Iterative BFS avoids recursion depth issues on deep skewed trees.

Approach

If root is None return None.
Push root into BFS queue.
While queue: pop node, swap node.left, node.right = node.right, node.left.
Push left and right children into queue if they exist.

Naive Solution — Recursive Swap

Recursively swap the left and right children.

Python

class Solution:
    def invertTree(self, root):
        if not root:
            return None

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

        root.left = right
        root.right = left

        return root

C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;

        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);

        root->left = right;
        root->right = left;

        return root;
    }
};

Java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        root.left = right;
        root.right = left;

        return root;
    }
}

JavaScript

var invertTree = function(root) {
    if (!root) return null;

    const left = invertTree(root.left);
    const right = invertTree(root.right);

    root.left = right;
    root.right = left;

    return root;
};

Time: O(n) · Aux Space: O(h) · Output Space: O(n) for tree

Optimized Code (Python 3)

Python

from collections import deque

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

C++

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            swap(node->left, node->right);

            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }

        return root;
    }
};

Java

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        return root;
    }
}

JavaScript

var invertTree = function(root) {
    if (!root) return null;

    const queue = [root];
    let head = 0;

    while (head < queue.length) {
        const node = queue[head++];

        [node.left, node.right] = [node.right, node.left];

        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }

    return root;
};

Time: O(n) · Aux Space: O(w)