package trees;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class MirrorBinaryTreeNodes {

    /*
     * Given the root node of a binary tree, swap the 'left' and 'right' children for each node.
     *
     * Runtime Complexity:
     * Linear, O(n)
     * Every sub-tree needs to be mirrored so we visit every node once and mirror the sub-tree starting there.
     * Hence run time complexity is O(n).
     *
     * Memory Complexity:
     * Linear, O(n) in the worst case.
     *
     * Do a post order traversal of the binary tree.
     * For every node, swap it's left child with right child.
     *
     *  */

    private static class Node {
        private int data;
        private Node left, right;

        Node(int item) {
            data = item;
            left = right = null;
        }

        public int getData() {
            return data;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }
    }


    private Node root1;
    protected void mirrorBinaryTree(Node root) {
        if (root == null) {
            return;
        }

        if (root.left != null) {
            mirrorBinaryTree(root.left);
        }

        if (root.right != null) {
            mirrorBinaryTree(root.right);
        }


        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
    }


    protected static void levelOrderTraversal(Node root) {

        if (root == null) {
            return;
        }

        List<Queue<Node>> queues = new ArrayList<>();
        queues.add(new ArrayDeque<>());
        queues.add(new ArrayDeque<>());

        Queue<Node> currentQueue = queues.get(0);
        Queue<Node> nextQueue = queues.get(1);

        currentQueue.add(root);
        int levelNumber = 0;

        while (!currentQueue.isEmpty()) {
            Node temp = currentQueue.poll();
            System.out.print(temp.data + ",");

            if (temp.left != null) {
                nextQueue.add(temp.left);
            }

            if (temp.right != null) {
                nextQueue.add(temp.right);
            }

            if (currentQueue.isEmpty()) {
                System.out.println();
                ++levelNumber;
                currentQueue = queues.get(levelNumber % 2);
                nextQueue = queues.get((levelNumber + 1) % 2);
            }
        }
        System.out.println();
    }
    

    public static void main(String[] argv) {
        MirrorBinaryTreeNodes tree = new MirrorBinaryTreeNodes();
        tree.root1 = new Node(1);
        tree.root1.left = new Node(2);
        tree.root1.right = new Node(3);
        tree.root1.left.left = new Node(4);
        tree.root1.left.right = new Node(5);
        tree.root1.right.left = new Node(6);
        tree.root1.right.right = new Node(7);        

        tree.levelOrderTraversal(tree.root1);
        tree.mirrorBinaryTree(tree.root1);
        tree.levelOrderTraversal(tree.root1);
    }
}