Invert Binary Tree

Thought Process

The Invert Binary Tree problem requires swapping the left and right children of every node in the tree. Here are two approaches:

Approach 1: Recursive Approach - Use a recursive function to traverse the tree. Swap the left and right children of each node recursively.

Approach 2: Iterative Approach (BFS) - Use a queue to perform a level-order traversal (BFS) of the tree. Swap the left and right children of each node during traversal. This approach avoids recursion and uses explicit memory for traversal.

Approach 1: Recursive Approach

/**
 * 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 == NULL)
            return root;

        if(root->left == NULL && root->right == NULL)
            return root;

        TreeNode *tmp = invertTree(root->left);
        root->left = invertTree(root->right);
        root->right = tmp;

        return root;
    }
};

Approach 2: Iterative Approach (BFS)

/**
 * 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 == NULL)
            return root;

        if(root->left == NULL && root->right == NULL)
            return root;

        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty()){

            TreeNode *nod = q.front(); q.pop();

            if(nod->left != NULL)
                q.push(nod->left);

            if(nod->right != NULL)
                q.push(nod->right);

            TreeNode *tmp = nod->left;
            nod->left = nod->right;
            nod->right = tmp;
        }
        return root;
    }
};

Code Complexity

Time Complexity: O(n)

Both approaches visit each node exactly once, ensuring linear time complexity.

Space Complexity: O(n)

The recursive approach uses O(h) space for the call stack, where h is the height of the tree. The iterative approach uses O(n) space for the queue in the worst case, where 'n' is the number of nodes in the tree.