Invert Tree - Amazon Top Interview Questions

                        Solution in C++ :

Tree* solve(Tree* root) {
    if (root == nullptr) {
        return root;
    }
    queue<Tree*> q;
    q.push(root);
    while (!q.empty()) {
        Tree* curr = q.front();
        q.pop();
        // swapping left and right nodes
        Tree* temp = curr->left;
        curr->left = curr->right;
        curr->right = temp;
        if (curr->left != nullptr) {
            q.push(curr->left);
        }
        if (curr->right != nullptr) {
            q.push(curr->right);
        }
    }
    return root;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    public Tree solve(Tree root) {
        return mirror(root);
    }
    static Tree mirror(Tree root) {
        if (root == null)
            return null;
        Tree left = mirror(root.left);
        Tree right = mirror(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        if root:
            dq = deque([root])
            while dq:
                node = dq.popleft()
                node.left, node.right = node.right, node.left
                if node.left:
                    dq.append(node.left)
                if node.right:
                    dq.append(node.right)
        return root