Invert binary tree

Given a binary tree, invert the binary tree - Inverting a binary tree means that the resulting binary tree should be a mirror replica of the input binary tree.

Example

Input

Binary Tree
                1
              /   \
            2       3
          /   \       \
        4       5       7
       /  \ 
    8       9

Output

Binary Tree
                1
              /   \
            3       2
          /       /   \
        7       5       4
                      /   \
                    9       8

Explanation

The resulting output binary tree is an exact mirror replica of the given input binary tree. Hence, the output is an inverted binary tree.

Constraints

0 <= N <=1000; 
N = Node value in a Binary Tree.