Invert Binary Tree solution and explanation
Google
9 more videos on this problem
Invert Binary Tree - Depth First Search - Leetcode 226NeetCode · 3:55 · 371K views
LeetCode Invert Binary Tree Solution Explained - JavaNick White · 5:59 · 103K views
Invert Binary Tree | Leetcode #226Techdose · 6:39 · 59K views
Invert Binary Tree - Leetcode 226 - Trees (Python)Greg Hogg · 6:40 · 24K views
Invert Binary Tree (LeetCode 226) | Full solution with diagrams and animations | Study AlgorithmsNikhil Lohia · 16:00 · 23K views
Leetcode 226. Invert Binary TreeFraz · 6:01 · 2K views
Invert Binary Tree - LeetCode 226 - JavaScriptAlgoJS · 3:03 · 2K views
INVERT BINARY TREE | LEETCODE # 226 | PYTHON SOLUTIONCracking FAANG · 8:48 · 2K views
Leetcode Visualized: 226 - Invert Binary TreeAlexander Le · 7:16 · 2K views
Invert Binary Tree | LeetCode 226 (Easy)Destination FAANG · 7:21 · 1K views
The problem
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return rootclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}#include <iostream>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return NULL;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function invertTree(root) {
if (root === null) return null;
const left = invertTree(root.left);
const right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) return NULL;
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode InvertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = InvertTree(root.left);
TreeNode right = InvertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}The Python solution uses a TreeNode class for node definition and a recursive method within a Solution class to inverse the tree recursively by swapping the nodes.
Time Complexity: O(n) where n is the number of nodes in the tree.
Space Complexity: O(h) due to 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.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None
queue = deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return rootimport java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
TreeNode temp = current.left;
current.left = current.right;
current.right = temp;
if (current.left != null) queue.add(current.left);
if (current.right != null) queue.add(current.right);
}
return root;
}
}#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return NULL;
std::queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
std::swap(current->left, current->right);
if (current->left) q.push(current->left);
if (current->right) q.push(current->right);
}
return root;
}function TreeNode(val, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
function invertTree(root) {
if (root === null) return null;
const queue = [];
queue.push(root);
while (queue.length > 0) {
const current = queue.shift();
[current.left, current.right] = [current.right, current.left];
if (current.left !== null) queue.push(current.left);
if (current.right !== null) queue.push(current.right);
}
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct QueueNode {
struct TreeNode *treeNode;
struct QueueNode *next;
};
struct Queue {
struct QueueNode *front, *rear;
};
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}
void enqueue(struct Queue* queue, struct TreeNode *node) {
struct QueueNode *newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
newNode->treeNode = node;
newNode->next = NULL;
if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}
queue->rear->next = newNode;
queue->rear = newNode;
}
struct TreeNode *dequeue(struct Queue* queue) {
if (queue->front == NULL)
return NULL;
struct QueueNode* temp = queue->front;
struct TreeNode *node = temp->treeNode;
queue->front = queue->front->next;
if (queue->front == NULL)
queue->rear = NULL;
free(temp);
return node;
}
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) return NULL;
struct Queue* queue = createQueue();
enqueue(queue, root);
while (queue->front != NULL) {
struct TreeNode* node = dequeue(queue);
struct TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
if (node->left) enqueue(queue, node->left);
if (node->right) enqueue(queue, node->right);
}
return root;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode InvertTree(TreeNode root) {
if (root == null) return null;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
TreeNode node = queue.Dequeue();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
return root;
}
}In this Python solution, the deque from the collections module is used to implement the queue-based iterative approach. Nodes are processed in a breadth-first manner and swapped in place.
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) due to the queue used in the solution.
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) {
return root;
}
const l = invertTree(root.left);
const r = invertTree(root.right);
root.left = r;
root.right = l;
return root;
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
l, r := invertTree(root.Left), invertTree(root.Right)
root.Left, root.Right = r, l
return root
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
pub fn invert_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
if let Some(node) = root.clone() {
let mut node = node.borrow_mut();
let left = node.left.take();
let right = node.right.take();
node.left = Self::invert_tree(right);
node.right = Self::invert_tree(left);
}
root
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Approach | Time Complexity: O(n) where n is the number of nodes in the tree. |
| Iterative Approach Using a Queue | Time Complexity: O(n) where n is the number of nodes. |
| Recursion | – |
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 |
Frequently asked questions
Is Invert Binary Tree easy or hard?
Invert Binary Tree is classified as an Easy problem. The logic is straightforward once you understand binary tree traversal, but it effectively tests recursion fundamentals and basic DFS or BFS implementation.
Invert Binary Tree Python/Java solution
Python and Java solutions usually implement a recursive DFS where each call swaps node.left and node.right, then recursively processes both children. The algorithm runs in O(n) time and uses O(h) stack space depending on the tree height.
How to solve Invert Binary Tree in O(n)?
Traverse the tree once and swap the left and right children at every node. This can be done using DFS recursion or BFS with a queue. Since each node is processed a single time, the algorithm runs in O(n) time.
What is the best approach for Invert Binary Tree?
The recursive DFS approach is the most common and concise solution. Swap the left and right children of each node, then recursively process the two subtrees. This visits every node exactly once, giving O(n) time complexity with O(h) recursion stack space where h is the tree height.
Is Invert Binary Tree asked at Google/Amazon/Meta?
Invert Binary Tree is a classic tree traversal problem that has appeared in interviews at companies like Google, Amazon, and Meta. It is commonly used to test understanding of recursion, binary tree structure, and DFS/BFS traversal patterns.
What data structure is used in Invert Binary Tree?
The problem operates on a binary tree data structure. Solutions typically use recursion (DFS with the call stack) or an explicit queue for BFS traversal to visit nodes and swap their children.
What is the time complexity of Invert Binary Tree?
The time complexity is O(n) because each node in the binary tree is visited exactly once and a constant-time swap operation is performed. Space complexity is O(h) for the recursive DFS approach or O(w) for the BFS queue approach, where h is height and w is maximum width.