Invert Binary Tree

Problem Description

Given the root of a binary tree, invert the tree, and return its root.

Examples

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 ≤ Node.val ≤ 100

Swapping Pointers Bottom-Up or Top-Down

To invert a binary tree, you must swap the left and right children of every node in the tree. This operation does not depend on the relationship between node values, making it applicable to any binary tree.

You can do this recursively. For each node, swap its left and right children, then recursively call the function on both child subtrees. Whether you swap the children first (pre-order) or recurse down first (post-order) is irrelevant, as long as every node is visited and its pointers swapped exactly once.

Solution 1: Recursive (Depth-First Search)

Use a post-order traversal to invert the child subtrees first, then swap the child pointers of the current node.

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

        // invert subtrees recursively
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // swap pointers
        root.left = right;
        root.right = left;

        return root;
    }
}

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

        # invert subtrees recursively
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)

        # swap pointers
        root.left = right
        root.right = left

        return root

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

        // invert subtrees recursively
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);

        // swap pointers
        root->left = right;
        root->right = left;

        return root;
    }
};

Complexity Analysis:

• Time Complexity: O(n) where n is the number of nodes in the tree. We visit each node exactly once.
• Space Complexity: O(h) where h is the tree height, which represents the call stack depth. In the worst case (skewed tree), space is O(n); for a balanced tree, it is O(log n).

Where it breaks: If the tree height is extremely large, deep recursion can trigger a stack overflow. In those cases, the iterative BFS approach below is safer.

Solution 2: Iterative (Breadth-First Search)

Use a queue to traverse the tree level by level, swapping the child pointers of each popped node.

import java.util.LinkedList;
import java.util.Queue;

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

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

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

            // swap child pointers
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;

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

        return root;
    }
}

from collections import deque


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

        queue = deque([root])
        while queue:
            curr = queue.popleft()

            # swap child pointers
            curr.left, curr.right = curr.right, curr.left

            if curr.left:
                queue.append(curr.left)
            if curr.right:
                queue.append(curr.right)

        return root

#include <queue>

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

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

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

            // swap child pointers
            TreeNode* temp = curr->left;
            curr->left = curr->right;
            curr->right = temp;

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

        return root;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We visit each node once.
• Space Complexity: O(w) where w is the maximum width of the tree. The queue stores at most the leaf nodes, which is O(n/2) = O(n) in the worst case.

Where it breaks: This method uses heap memory for the queue instead of call stack frames. It avoids stack overflow but can still run out of memory on exceptionally wide trees.

Common Mistakes

• Swapping only the values instead of the node references. Swapping values is slower and can violate the identity of the tree structure.
• Losing reference to a child node before completing the swap. When writing in Java or C++, store one child in a temporary variable before overwriting it.
• Traversing the swapped nodes recursively. If you swap the left and right children first, and then recurse using the new paths, you might end up inverting the same subtree twice, resulting in no change at all.

Frequently Asked Questions

Is this the problem that became famous because of a tweet? Yes. Max Howell (creator of Homebrew) tweeted that Google rejected him because he could not invert a binary tree on a whiteboard, despite most of Google’s engineers using Homebrew.

Does this algorithm work for non-binary trees? Yes. For an n-ary tree, you would reverse the list of children pointers for every node.

What does this problem test in interviews? It tests your basic understanding of tree structure, pointer manipulation, and recursive traversal flow.

← All Problems