/*
using DFS recursive method to do it.
Complexity Analysis

Since each node in the tree is visited only once, the time complexity is O(n), where n is the number of nodes in the tree. We cannot do better than that, since at the very least we have to visit each node to invert it.

Because of recursion, O(h) function calls will be placed on the stack in the worst case, where h is the height of the tree. Because h∈O(n), the space complexity is O(n).
*/


public class Solution {
    public TreeNode invertTree(TreeNode root) {

        //base case
        if (root == null){
            return null;
        }

        //recursive part
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;

    }
}

/* 
using BFS iterative method using Queue(LinkedList)
The idea is that we need to swap the left and right child of all nodes in the tree. So we create a queue to store nodes whose left and right child have not been swapped yet. Initially, only the root is in the queue. As long as the queue is not empty, remove the next node from the queue, swap its children, and add the children to the queue. Null nodes are not added to the queue. Eventually, the queue will be empty and all the children swapped, and we return the original root.

Complexity Analysis

Since each node in the tree is visited / added to the queue only once, the time complexity is O(n), where nn is the number of nodes in the tree.

Space complexity is O(n), since in the worst case, the queue will contain all nodes in one level of the binary tree. For a full binary tree, the leaf level has n/2 = O(n) leaves.
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root==null) {
            return root;
        }

        Queue<TreeNode> myQ = new LinkedList<TreeNode>();
        myQ.add(root);
        while(!myQ.isEmpty()) {
            TreeNode cur = myQ.poll();
            //swap stage
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            if (cur.left!=null) {
                myQ.add(cur.left);
            }
            if(cur.right!=null) {
                myQ.add(cur.right);
            }
        }
        return root;
    }
}