DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Invert Binary Tree

easyTrees

Problem statement

Given the root of a binary tree, turn it into its mirror image: at every node, the left and right children swap places. Return the root of the changed tree.

Trees are written in level order, with null for a missing child.

Examples

Example 1

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

Output: [6, 9, 2, 10, 7, 4, 1]

Example 2

Input: root = [3, 1]

Output: [3, null, 1]

Explanation: The left child 1 becomes the right child.

Hints

Approach

Mirror the two subtrees recursively, then attach them to the opposite sides.

  1. If root is empty, return it.
  2. Invert the left subtree and the right subtree.
  3. Set root.left to the inverted right subtree and root.right to the inverted left subtree.
  4. Return root.

In Python the tuple assignment evaluates both recursive calls before assigning, so nothing is overwritten early. In Java, keep the left result in a variable before reassigning. Each node is visited once, and the stack depth equals the tree's height.

ComplexityTime O(n)Space O(h), where h is the height of the tree
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional["TreeNode"]) -> Optional["TreeNode"]:
if root is None:
return None
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root

Follow-up questions

  • Check whether a tree is symmetric, meaning it equals its own mirror, without modifying it.
  • Invert the tree iteratively using a stack instead of a queue.

Frequently asked questions

No. Pre-order (swap, then recurse) and post-order (recurse, then swap) both swap every node exactly once. The one mistake to avoid is an in-order swap that recurses into the same side twice, which leaves some subtrees unchanged.

The problem expects the tree to be changed in place and the same root returned. If the caller needs the original, create new nodes at each step instead; the recursion shape is identical, and the space becomes O(n).

It checks that you can write clean recursion on a tree and reason about pointer updates without losing a subtree. That skill carries over directly to walking directory trees, dependency trees and nested config.