Easy Trees ⭐ Viral Interview Question

Invert a Binary Tree — Recursive & BFS Solution (Python, C, JS)

Problem Statement

Given the root of a binary tree, mirror the tree so every node's left and right children are swapped. Return the root.

Example
Input: root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]
Time Complexity
O(n)
Space Complexity
O(h) recursion stack

The Intuition

Recursive DFS — swap left and right at each node, then recurse into both children.

Solution Code

def invertTree(root):
    if not root: return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root
struct TreeNode* invertTree(struct TreeNode* root) {
    if (!root) return NULL;
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
function invertTree(root) {
    if (!root) return null;
    [root.left, root.right] = [root.right, root.left];
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

Frequently Asked Questions

Q: Why is this problem famous?
The creator of Homebrew (brew) was rejected by Google because he couldn't whiteboard this. It went viral.

Practice These Problems in a Real Curriculum

DoxaTech Hub's 10-month programme covers Data Structures, Algorithms, Python, C, SQL, and Full-Stack Development through 40 weeks of real, graded projects.

Get Started → More Problems