Log inSign up
easyleetcodeNot Started

Invert Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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

Inverting a tree swaps every node's left child with its right child throughout the entire tree, creating a mirror image.

Example 1 · Example 1: Balanced Tree:

Input: root = [4, 2, 7, 1, 3, 6, 9] Tree: 4 / \ 2 7 / \ / \ 1 3 6 9
Output: [4, 7, 2, 9, 6, 3, 1]
Explanation: Mirror image swaps 2 and 7, 1 and 9, 3 and 6.

Example 2 · Example 2: 3-Node Tree:

Input: root = [2, 1, 3] Tree: 2 / \ 1 3
Output: [2, 3, 1]
Explanation: Left child 1 and right child 3 are swapped.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master pointer swapping on binary tree nodes.
  • Recognize recursive and iterative equivalents of tree transformations.
  • Understand why both preorder and postorder traversals succeed.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Mirror binary tree.
  • Invert left and right subtrees.
  • Symmetric reflection.

Algorithmic Decision Tree:

  • If root == null -> return null.
  • swap(root.left, root.right).
  • invert(root.left); invert(root.right).
  • return root.

Connected Patterns:

Symmetric TreeFlip Equivalent Binary TreesFlatten Binary Tree to Linked List

1. Clone Mirror Tree Recursively

Intuition

Create a new TreeNode for root, and set its left to cloneInvert(root.right) and its right to cloneInvert(root.left).

When to apply: When the input tree must remain immutable.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: Create new TreeNode copy(root.val).
  3. Step 3: copy.left = cloneInvert(root.right).
  4. Step 4: copy.right = cloneInvert(root.left). Return copy.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* invertTree(TreeNode* root) {
10 if (!root) return nullptr;
11 TreeNode* copy = new TreeNode(root->val);
12 copy->left = invertTree(root->right);
13 copy->right = invertTree(root->left);
14 return copy;
15 }
16};
17
18int main() {
19 // Sample driver execution
20 cout << "Execution completed successfully." << endl;
21 return 0;
22}
23

Time & Space Complexity

  • Time complexity: O(n) — Allocates n new nodes.
  • Space complexity: O(n) — O(n) new memory for copied tree nodes.

2. Iterative BFS Queue Inversion

Intuition

Push root into queue. While queue not empty: pop node, swap node.left and node.right. If left exists, enqueue left; if right exists, enqueue right.

When to apply: Iterative alternative avoiding recursion call stack.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: Queue q with root.
  3. Step 3: While q not empty: pop node.
  4. Step 4: swap(node.left, node.right).
  5. Step 5: Enqueue non-null children. Return root.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* invertTree(TreeNode* root) {
10 if (!root) return nullptr;
11 queue<TreeNode*> q;
12 q.push(root);
13 while (!q.empty()) {
14 TreeNode* cur = q.front(); q.pop();
15 swap(cur->left, cur->right);
16 if (cur->left) q.push(cur->left);
17 if (cur->right) q.push(cur->right);
18 }
19 return root;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum level width w.

3. In-Place Recursive DFS

Intuition

Base case: if root == null return null. Swap left and right subtrees: let temp = root.left; root.left = invertTree(root.right); root.right = invertTree(temp). Return root.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: If root == null return null.
  2. Step 2: Save temp = root.left.
  3. Step 3: root.left = invertTree(root.right).
  4. Step 4: root.right = invertTree(temp).
  5. Step 5: Return root.

Inversion Trace for root = [2, 1, 3]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Inspect root 2
Visual state
Values and pointers at this exact step
tree
Root
2
L
1
R
3

Node order shown; add connections to display explicit tree edges.

swap: 2
Check / comparison
Left = 1, Right = 3 before swap
Decision / next transition
Swap left and right pointers of root 2.
Why this step matters

Step 1: Inspect root 2. Left child is 1, Right child is 3.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 TreeNode* invertTree(TreeNode* root) {
10 if (!root) return nullptr;
11 TreeNode* temp = root->left;
12 root->left = invertTree(root->right);
13 root->right = invertTree(temp);
14 return root;
15 }
16};
17
18int main() {
19 // Sample driver execution
20 cout << "Execution completed successfully." << endl;
21 return 0;
22}
23

Time & Space Complexity

  • Time complexity: O(n) — Processes each node once in O(1) time.
  • Space complexity: O(h) — Recursion call stack equals tree height h.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Clone Mirror TreeO(n)O(n)Allocate new nodes rather than mutating input.Memory allocation.
2.Iterative BFS QueueO(n)O(w)Queue swaps children of each popped node.Queue.
3.In-Place Recursive DFSOptimalO(n)O(h)Recursive in-place pointer swap.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: root = [] -> returns [].
  • Single node: root = [1] -> returns [1].
  • Asymmetric tree: correctly inverts null pointers with existing subtrees.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Demonstrate both recursive and iterative (BFS queue) versions to show depth of understanding.
  2. Note that in-order traversal requires care (swapping in the middle would invert the left subtree twice).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does standard in-order traversal (left, swap, right) NOT correctly invert a binary tree without modification?

Back to DSA Sheet