LeetEye LeetEye
Medium Tree Traversal ~5 min

Invert Binary Tree

trees invert-binary-tree

Problem

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

Inverting a binary tree means swapping every left child with its corresponding right child.

Examples

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

At each node, swap its left and right children. Then recursively do the same for each child.

At each node, swap left and right children. Recursively invert both subtrees. Return root.

How to Approach This Problem

Pattern Recognition: When you see keywords like invert binary tree trees, think Tree Traversal.

Step-by-Step Reasoning

1 For a null node, we:
Answer: Return null
Nothing to swap in an empty tree. Just return null.
2 At each node, we swap:
Answer: Left and right child pointers
Swap the subtrees, not values. Node keeps its value, but its children switch sides.
3 At each node, we can:
Answer: Either order works
Swap first, then invert children. Or invert children first, then swap. Both produce correct result.
4 After swapping, we:
Answer: Invert both children recursively
Each subtree needs to be inverted too. Recurse on both.
5 After inverting, we return:
Answer: The original root
Return the (now inverted) root so caller can connect it.
6 Iteratively, we can use:
Answer: BFS or DFS with queue/stack
Visit each node (any order), swap its children. Queue (BFS) or stack (DFS) both work.

Solution

def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None
    
    # Swap left and right children
    root.left, root.right = root.right, root.left
    
    # Recursively invert subtrees
    invertTree(root.left)
    invertTree(root.right)
    
    return root

Complexity Analysis

Time O(n)
Space O(h)

Master This Pattern

Build intuition with interactive MCQs. Practice Tree Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye