Invert Binary Tree

easy
TreesTreeBinary TreeDepth-First SearchBreadth-First Search

Given the root of a binary tree, invert the tree and return its root. Inverting a binary tree means swapping the left and right children of every node in the tree.

Examples

Example 1

  • Input: root = [4,2,7,1,3,6,9]
  • Output: [4,7,2,9,6,3,1]
  • Explanation: Every node's left and right children are swapped.

Example 2

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

Example 3

  • Input: root = []
  • Output: []

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive DFS

Intuition

The recursive approach is the most elegant way to invert a binary tree. For each node, we simply swap its left and right children, then recursively invert each subtree. The base case is a null node, which we return as-is. The recursion naturally handles all nodes in the tree, and after every subtree has been inverted, the entire tree is inverted. The order of operations (swap then recurse, or recurse then swap) does not matter since both produce the correct result.

Algorithm

  1. If the root is null, return null (base case).
  2. Swap the left and right children of the current node.
  3. Recursively invert the left subtree.
  4. Recursively invert the right subtree.
  5. Return the root.
TimeO(n)SpaceO(h) where h is the height of the tree

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};
Java 21
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}
Python 3.12
def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root
Go 1.26
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = root.Right, root.Left
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}
Approach 2

Iterative BFS

Intuition

We can invert the tree level by level using a queue. Starting from the root, we process each node by swapping its children, then adding the non-null children to the queue for further processing. This approach avoids recursion and is useful when the tree might be very deep (avoiding stack overflow). The BFS order does not affect correctness since every node is visited exactly once and its children are swapped.

Algorithm

  1. If the root is null, return null.
  2. Initialize a queue with the root node.
  3. While the queue is not empty, dequeue a node.
  4. Swap the left and right children of the dequeued node.
  5. If the left child is not null, add it to the queue.
  6. If the right child is not null, add it to the queue.
  7. Return the root.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) 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 21
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        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;
    }
}
Python 3.12
from collections import deque


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    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
Go 1.26
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        node.Left, node.Right = node.Right, node.Left
        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }
    return root
}

Frequently asked questions

What is the optimal time complexity of Invert Binary Tree?

The most efficient approach in this guide ("Iterative BFS") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Invert Binary Tree use?

Invert Binary Tree is a easy-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Invert Binary Tree be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) where h is the height of the tree, while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
root=
[4,2,7,1,3,6,9]
Expected Output
[4,7,2,9,6,3,1]