Given a binary tree, the task is create a mirror tree from it.
Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.
Mirror of a Binary Tree
Solutions
Method 1: Recursion
We can solve this problem with recursion, the idea is to get mirror of 'left' and 'right' sub-trees of current node recursively and swap 'left' sub-tree with 'right'.
Complexity
The time complexity of this solution is O(n) and space complexity is also O(n) for call stack.
Method 2: Iterative approach
We can solve this problem with iterative approach, the idea is to perform queue based level order traversal and swap right, left children (sub-trees) of each node.
Complexity
The time complexity of this solution is O(n) and space complexity is also O(n) for extra memory taken by Queue.