ToolMight LogoToolMight
EasyTrees & BSTPattern: DFS TraversalPattern: Recursive Tree Inversion

Invert Binary Tree

Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.

Problem Statement

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

Examples & Constraints

Example 1
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
Explanation: Each node has its left and right children swapped recursively.
Example 2
Input: root = [2, 1, 3]
Output: [2, 3, 1]
Explanation: Children 1 and 3 are inverted.
Constraints
  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Depth-First Search (Recursive Swap)

Optimal Approach
Time:O(n)
Space:O(h)

Recursively swap the left and right children for every node down to leaf nodes.

Time ComplexityO(n)

Every node in the tree of size N is visited exactly once.

Space ComplexityO(h)

Consumes memory proportional to the height of the tree H on the recursion call stack (O(log n) for balanced tree, O(n) for skewed tree).

Underlying algorithmic logic

The Core Mental Model: The Mirror Reflection

Imagine standing in front of a mirror: your left hand appears on the right side, and your right hand appears on the left side.

At any node in a binary tree:

  1. Swap your left child pointer and your right child pointer.
  2. Tell your new left child to mirror itself recursively.
  3. Tell your new right child to mirror itself recursively.

The Recursive Contract

Because a binary tree is self-similar (every subtree is itself a complete binary tree), a function that successfully inverts one node can invert the entire tree:

  • Base Case: If root == null, there are no children to swap -> return null.
  • Recursive Step:
  temp = root.left
  root.left = invertTree(root.right)
  root.right = invertTree(temp)
  return root

Every single node is visited and swapped exactly once, making the algorithm an optimal `O(n)` time operation. Memory is bounded strictly by the height of the tree O(h) on the call stack.

Step-by-step execution walkthrough

1
Root Node (4)

Swap left child (2) with right child (7).

root(4) has left(7) and right(2)
2
Left Subtree (7)

Recursively invert node 7: swap child 6 and 9 to become 9 and 6.

node(7) has left(9) and right(6)
3
Right Subtree (2)

Recursively invert node 2: swap child 1 and 3 to become 3 and 1.

node(2) has left(3) and right(1)
Advantages
  • •Optimal O(n) runtime
  • •Clean, concise recursive structure
Trade-offs
  • •Recursion depth bounded by tree height

Code Implementations

Copy & paste production-ready solutions for Depth-First Search (Recursive Swap) in your language of choice

File: solution.py
Python
from __future__ import annotations
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None):
        self.val = val
        self.left = left
        self.right = right
def invert_tree(root: TreeNode | None) -> TreeNode | None:
    if not root:
        return None
    root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root
def print_in_order(root: TreeNode | None) -> str:
    result: list[int] = []
    def traverse(node: TreeNode | None) -> None:
        if not node:
            return
        traverse(node.left)
        result.append(node.val)
        traverse(node.right)
    traverse(root)
    return " ".join(map(str, result))
if __name__ == "__main__":
    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(7, TreeNode(6), TreeNode(9))
    )
    print("In-order before inversion:", print_in_order(root))
    invert_tree(root)
    print("In-order after inversion: ", print_in_order(root))
Interactive visualizer available

Understand Binary Search Tree Visually

Explore hierarchical parent-child nodes, traversal modes (in-order, pre-order, post-order), and search lookups. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Tree Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyLinked List
Visualizer

Reverse Linked List

Reverse the directional arrows of a singly linked list in-place. The classic test of reference manipulation and memory pointer management.

2 approaches(O(n))
Learn logic
EasyBinary Search
Visualizer

Binary Search

Locate a target value in a sorted array in O(log n) logarithmic time. Like opening a dictionary in the middle, each comparison eliminates half the remaining items.

2 approaches(O(log n))
Learn logic