Invert Binary Tree

Easy Problem 64 of 151 Java and Python

Practice on LeetCode

Problem

Given the root of a binary tree, invert it (mirror it left to right) and return its root.

Example 1

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

Example 2

Input: root = [2, 1, 3]
Output: [2, 3, 1]

Constraints

0 ≤ number of nodes ≤ 100

Explanation

Mirroring the whole tree is the same as swapping the two children of every node. The order you visit the nodes in does not matter.

Approach 1 · Better

BFS, swap at each node

Time O(n)
Space O(w)

Visit nodes with a queue and swap each node's children.

Add the root to a queue.
Pop a node, swap left and right, add its non-null children.

Java

import java.util.*;

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return root;
    }
}

Python

from collections import deque

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        queue = deque([root] if root else [])
        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

Approach 2 · Optimal

Recursion

Time O(n)
Space O(h)

Invert both subtrees, then attach them swapped.

If root is null, return null.
Set left = invertTree(root.right), right = invertTree(root.left); assign them and return root.

Java

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

Python

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

Complexity compared

Approach	Time	Space
Better BFS, swap at each node	O(n)	O(w)
Optimal Recursion	O(n)	O(h)

Key takeaways

In Java, store the recursive results before assigning; writing root.left = invertTree(root.right) first would lose the original left subtree.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem