Invert Binary Tree

Practice here

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

Recursion Approach#

• Intuition: Inverting a tree means every node's left and right children are swapped. Because the tree is recursive by nature, swapping children at each node and then recursing into both subtrees is all that is needed.
• Mechanics: At each node, swap left and right pointers first, then recurse into the (now-swapped) left and right children. The null base case stops recursion at leaves. Because the swap happens before the recursive calls, this is effectively a pre-order traversal.
• Trade-off: The recursive solution is concise and mirrors the tree's own recursive structure, but uses O(h) call-stack space. For a balanced tree this is O(log n); for a skewed tree it reaches O(n).

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:

    void invertTreeUtil(TreeNode* root)
    {
        if(!root)
            return;
        if(root->left || root->right)
            swap(root->left, root->right);

        invertTree(root->left);
        invertTree(root->right);
    }

    TreeNode* invertTree(TreeNode* root) {
        invertTreeUtil(root);
        return root;
    }
};

Time Complexity: O(n), Each node visited once

Space Complexity: O(h), Recursion stack

Iterative Approach#

• Intuition: The same swap-children-at-every-node logic can be driven iteratively with a queue (BFS) instead of recursion. Each dequeued node has its children swapped, and both children are then enqueued to be processed in subsequent iterations.
• Mechanics: Push the root onto the queue. On each iteration, pop the front node, swap its left and right children, then push the non-null children. This continues until the queue is empty, guaranteeing every node is visited exactly once.
• Trade-off: Avoids stack overflow on deep trees, but uses O(w) queue space where w is the maximum width of the tree (O(n) in the worst case). This is generally larger than the O(h) stack of the recursive approach for balanced trees.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root)
            return NULL;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            TreeNode* currNode = q.front();
            q.pop();

            if(currNode->left || currNode->right)
                swap(currNode->left, currNode->right);

            if(currNode->left)
                q.push(currNode->left);

            if(currNode->right)
                q.push(currNode->right);
        }

        return root;
    }
};

Time Complexity: O(n), Each node visited once

Space Complexity: O(n), the queue can store all the nodes of the last level.