Coding Interview PatternsInvert Binary Tree
EasyTree Depth-First Search

Invert Binary Tree

Explanation & Solution

Practice Problem

Description

Given the root of a binary tree, invert the tree by swapping the left and right children of all nodes and return its root.

Examples

Example 1:

```tree

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

`

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

Explanation: The tree is mirrored — every left child is swapped with its corresponding right child.

Example 2:

```tree

[2, 1, 3]

`

Input:root = [2, 1, 3]
0
2
1
1
2
3
Output:[2, 3, 1]
0
2
1
3
2
1

Example 3:

Input: root = []

Output: []

Constraints

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

Approach

Tree Depth-First Search pattern

1. Base Case

  • If root is null:
  • Return null
  • Reason:
  • An empty tree is already inverted

2. Swap Children

  • Store root.left in a temporary variable
  • Set root.left = root.right
  • Set root.right = temp
  • This swaps the left and right subtrees at the current node

3. Recurse on Left Subtree

  • Call solve(root.left)
  • This inverts all nodes in the left subtree

4. Recurse on Right Subtree

  • Call solve(root.right)
  • This inverts all nodes in the right subtree

5. Return the Root

  • After swapping and recursing:
  • Return root
  • The entire tree is now mirrored

Key Insight

  • At every node, we simply swap left and right
  • Recursion ensures this happens at every level of the tree
Time
O(n)visit each node once
Space
O(h)recursion stack where h is tree height

Visualization

Input:
DFS Traversal[4, 2, 7, 1, 3, 6, 9]
4271369
output0

Press play to start DFS traversal

CurrentIn stackComplete
15 steps

Solution Code

Previous
Diameter of Binary Tree
Next
Maximum Depth of Binary Tree