How do you solve Invert Binary Tree?

Use a recursive DFS approach. For each node, swap its left and right children, then recursively call the inversion function on the new left and right children. The recursion naturally terminates at leaf nodes or null children. This approach is simple, elegant, and runs in O(n) time with O(h) space due to recursion stack, where h is the tree height.

What pattern does Invert Binary Tree use?

The Pattern: DFS (Recursive Tree Traversal) The Heuristic: When a problem requires applying a transformation to every node in a tree, a recursive DFS that processes the current node and then recurses on children is the most natural and efficient approach.

Invert Binary Tree — DFS

Q: What is the time complexity of Invert Binary Tree?

O(n). Each node is visited exactly once to perform the swap operation, resulting in linear time proportional to the number of nodes.

Problem

Given the root of a binary tree, invert the tree and return its root such that the left and right children of all nodes are swapped.

The number of nodes in the tree is in the range [0, 100].
−100 ≤ Node.val ≤ 100

Example

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

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

Starting at the root node with value 4, the algorithm swaps its left child (2) and right child (7). Then it recursively inverts the left subtree rooted at 7 and the right subtree rooted at 2. For node 7, its children 6 and 9 are swapped. For node 2, its children 1 and 3 are swapped. This process continues recursively until all nodes have their children swapped, resulting in the inverted tree.

Approach

Straightforward Solution

A brute-force approach might attempt to collect all nodes and then swap children iteratively, but this requires extra space and complicates traversal order. Alternatively, a level-order traversal could be used, but it is more complex and less natural for this problem.

Core Observation

Inverting a binary tree is a structural transformation where each node's left and right children are swapped. This operation must be applied recursively to every node in the tree to achieve a full inversion.

Path to Optimal

Preview

The key insight is that the inversion operation is naturally recursive: inverting a tree is equivalent to swapping the children of the root and then recursively inverting the left and right subtrees…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS approach. For each node, swap its left and right children, then recursively call the inversion function on the new left and right children…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is visited exactly once to perform the swap operation, resulting in linear time proportional to the number of nodes.

Space

O(h)

The recursion stack depth is proportional to the height of the tree, which is O(h). This is the auxiliary space used, excluding the input and output tree structures.

Solution

Python

1class Solution:
  def invertTree(self, root: TreeNode) -> TreeNode:
      if not root:
          return None
      
      root.left, root.right = root.right, root.left
7
      self.invertTree(root.left)
      self.invertTree(root.right)
      
      return root

Step-by-Step Solution

1

Return None for Empty Tree to Handle Base Case

3if not root:
4    return None

Objective

To immediately return None when the current node is null, terminating recursion at leaf boundaries.

Key Insight

The base case of the recursion is critical to prevent infinite recursion and to correctly handle empty subtrees. Returning None when the node is null ensures that leaf nodes' children are handled gracefully and recursion unwinds properly.

Interview Quick-Check

Core Logic

The base case check `if not root: return None` prevents further recursion and correctly handles empty subtrees.

State & Boundaries

This base case defines the recursion boundary, ensuring the algorithm terminates at leaf nodes.

2

Swap Left and Right Children to Invert Current Node

To invert the current node by swapping its left and right child pointers.

3

Recursively Invert Left and Right Subtrees After Swap

To recursively apply the inversion operation to the subtrees rooted at the swapped children.

4

Return Root to Provide Inverted Tree to Caller

To return the root node of the inverted subtree to the caller, enabling reconstruction of the full inverted tree.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 6 Critical

root.left, root.right = root.right, root.left

Swap the left and right children of the current node.

This in-place swap is the fundamental operation that inverts the tree structure at the current node, enabling the recursive inversion to propagate correctly.

Line 3 Critical

if not root:

Check if the current node is null to handle the base case.

This base case prevents infinite recursion by terminating the traversal when a leaf's child is reached, which is essential for correctness.

Line 8 Critical

self.invertTree(root.left)

Recursively invert the left subtree after swapping.

Recursing on the swapped left child ensures the entire left subtree is inverted, maintaining the correctness of the full inversion.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does swapping the children before the recursive calls not affect the correctness of the inversion?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Invert Binary Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Invert Binary Tree drill

or drill a free problem

1	`class Solution:`
2	`def invertTree(self, root: TreeNode) -> TreeNode:`
3	`if not root:`
4	`return None`
5
6	`root.left, root.right = root.right, root.left`
7
8	`self.invertTree(root.left)`
9	`self.invertTree(root.right)`
10
11	`return root`