#226

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Invert Binary Tree

Invert Binary Tree swaps every node's left and right children using tree traversal, with recursive DFS or iterative BFS both fitting cleanly.

tree depth first search breadth first search binary tree

Problem Statement

You are given the root of a binary tree and need to reverse its structure in place by exchanging the left and right child of every node. After all swaps are applied across the tree, return the root of the inverted tree.

For example, a tree represented by root = [4,2,7,1,3,6,9] becomes [4,7,2,9,6,3,1] because each parent flips its two children all the way down. The tree can be empty, and the total node count is small enough that either recursive depth-first traversal or iterative breadth-first traversal is acceptable.

Examples

Example 1

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

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

Example details omitted.

Example 2

Input: root = [2,1,3]

Output: [2,3,1]

Example details omitted.

Example 3

Input: root = []

Output: []

Example details omitted.

Constraints

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

Solution Approach

Use the repeated swap pattern at each node

This problem is a binary-tree traversal where the state update is always the same: swap the current node's left and right pointers. Once you recognize that no comparison or balancing logic is needed, the task becomes visiting every node exactly once and applying that swap safely.

Recursive DFS keeps the code closest to the tree definition

At each node, first handle the base case where the node is null. Otherwise swap its children, then recursively invert the new left subtree and new right subtree. This mirrors the recursive structure of a binary tree, which is why LeetCode 226 is often solved fastest with preorder-style DFS.

Iterative BFS is a clean alternative when you want explicit control

Start with the root in a queue. Pop one node at a time, swap its children, then push any non-null children back into the queue. This avoids recursion depth concerns and makes the traversal order level by level, but the actual inversion logic is identical: every node gets one swap.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Both DFS and BFS visit each node once, so the time complexity is O(n). The extra space is O(h) for recursive DFS, where h is tree height, or O(w) for BFS, where w is the maximum width of the tree. In the worst case, either approach can use O(n) extra space, but for this problem's small constraints the practical difference is usually about implementation style, not performance.

What Interviewers Usually Probe

They want to see that you reduce the problem to one local operation repeated over the whole tree: swap left and right at every node.
They may ask for both recursive DFS and iterative BFS to check whether you understand traversal choice versus inversion logic.
They are watching for whether you handle the empty tree immediately and return the original root reference after mutation.

Common Pitfalls or Variants

Common pitfalls

Recursing before preserving or swapping child pointers correctly, which can make the traversal harder to reason about.
Overcomplicating the solution with extra arrays or rebuilding nodes when the problem only needs pointer swaps in place.
Forgetting that an empty tree is valid input and should return an empty result without further work.

Follow-up variants

Invert the tree iteratively with a stack instead of recursion, using the same swap-at-each-node rule.
Return a new inverted tree without mutating the original, which changes the trade-off from pointer swapping to node reconstruction.
Invert only nodes below a certain depth, where traversal still matters but the swap condition becomes selective.

FAQ

What is the easiest way to solve Invert Binary Tree?

The easiest solution is recursive DFS. For each node, swap left and right, then recursively invert both subtrees. That keeps the code short and matches the structure of the tree.

Is BFS also valid for LeetCode 226?

Yes. A queue-based BFS works perfectly because the operation at every node is independent of traversal order. You still visit each node once and swap its two children once.

What pattern does Invert Binary Tree use?

The main pattern is binary-tree traversal with a local state update at each node. In this problem, that state update is specifically swapping the left and right child pointers.

Do I need to create a new tree for this problem?

No. The standard solution mutates the existing tree in place and returns the same root reference. Creating a new tree is possible, but it adds unnecessary work unless the variant requires immutability.

What usually goes wrong in interviews on this problem title?

Candidates often make it harder than it is. The typical mistake is adding extra structure or getting confused about recursion order, when the real requirement is just to swap children at every visited node and handle null correctly.

terminal

Solution

Solution 1: Recursion

First, we check if $\textit{root}$ is null. If it is, we return $\text{null}$. Then, we recursively invert the left and right subtrees, set the inverted right subtree as the new left subtree, and set the inverted left subtree as the new right subtree. Finally, we return $\textit{root}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

# Definition for a binary tree node.
# 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
        l, r = self.invertTree(root.left), self.invertTree(root.right)
        root.left, root.right = r, l
        return root

Continue Practicing

#199 binary tree right side view #297 serialize and deserialize binary tree #117 populating next right pointers in each node ii