Invert Binary Tree - Solution & Explanation
Problem Statement
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3] Output: [2,3,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 Overview
Problem Overview: You are given the root of a binary tree. The task is to invert the tree by swapping the left and right children of every node. After inversion, all left pointers become right pointers and vice versa across the entire structure.
Approach 1: Recursive DFS (O(n) time, O(h) space)
This approach uses recursion with Depth-First Search. Starting from the root, swap its left and right children, then recursively apply the same operation to both subtrees. The key insight is that every node can be processed independently once you reach it. Because each node is visited exactly once, the time complexity is O(n), where n is the number of nodes. The recursion stack uses O(h) space, where h is the tree height (worst case O(n) for a skewed tree, O(log n) for balanced trees). This approach is short, readable, and commonly expected in interviews.
Approach 2: Iterative BFS Using a Queue (O(n) time, O(w) space)
This version processes the tree level by level using Breadth-First Search. Push the root into a queue. While the queue is not empty, pop the current node, swap its left and right pointers, then push the children back into the queue. Each node is visited once, so the runtime remains O(n). The queue can hold up to the maximum number of nodes at a level, which leads to O(w) auxiliary space where w is the maximum width of the tree.
Both strategies operate directly on the structure of a binary tree. The recursive DFS version focuses on subtree transformations, while the BFS version processes nodes in level order. Neither approach requires extra data structures beyond the recursion stack or queue.
Recommended for interviews: The recursive DFS solution is the most common answer. It demonstrates clear understanding of tree traversal and requires only a few lines of code. The BFS queue approach is equally valid and useful if you prefer iterative logic or want to avoid recursion depth limits. Showing both approaches signals strong mastery of tree traversal patterns.
Approach 1: Recursive Approach
This approach employs recursion to invert the binary tree. The basic idea is to traverse the tree and swap the left and right children of every node recursively. We recursively call the function on the left and right subtrees until we reach the base case, which is when the node is null.
This C solution defines a struct for the tree node, and then uses a recursive function invertTree that swaps the left and right children of each node starting from the root. The recursion continues until all nodes have been swapped.
Complexity
Time Complexity: O(n) where n is the number of nodes in the tree, because each node is visited once.
Space Complexity: O(h) where h is the height of the tree, for the recursion stack.
Approach 2: Iterative Approach Using a Queue
The iterative approach involves using a queue or stack to traverse the tree level by level (or depth by depth) while inverting the child nodes by putting the left child in place of the right child and vice versa for each node. This is effectively a breadth-first traversal that swaps children iteratively.
The C solution uses a queue data structure to perform a breadth-first traversal. For each node, it swaps the left and right children and then enqueues the children nodes if they exist.
Complexity
Time Complexity: O(n) where n is the number of nodes in the tree.
Space Complexity: O(n) due to the queue data structure.
Approach 3: Recursion
First, we check if root is null. If it is, we return null. Then, we recursively invert the left and right subtrees, set the inverted right subtree as the new left subtree, and set the inverted left subtree as the new right subtree. Finally, we return root.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) where n is the number of nodes in the tree, because each node is visited once. |
| Iterative Approach Using a Queue | Time Complexity: O(n) where n is the number of nodes in the tree. |
| Recursion | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(n) | O(h) | Best for interviews and clean implementations when recursion depth is safe |
| Iterative BFS with Queue | O(n) | O(w) | Useful when avoiding recursion or when working level-by-level |
Video Solution
Invert Binary Tree - Depth First Search - Leetcode 226 • NeetCode • 371,598 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Invert Binary Tree easy or hard?
Invert Binary Tree Python/Java solution
How to solve Invert Binary Tree in O(n)?
What is the best approach for Invert Binary Tree?
Is Invert Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Invert Binary Tree?
What is the time complexity of Invert Binary Tree?
Ready to solve this problem?
Practice Invert Binary Tree with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor