Create a mirror tree from a given binary tree

Posted by on Mar 31, 2024

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.

Related


Print the left view of a binary tree

Print diagonal traversal of a binary tree

Write a program to print height/depth of a Binary Tree

Print a Binary Tree in Vertical Order

Print Nodes in Top View of a Binary Tree

Print/Traverse a Binary Tree in Zigzag Order

Level Order or Breadth First traversal of Binary Tree

Find the diameter or width of a binary tree

In-order Tree Traversal - Iterative and Recursive

Pre-order Tree Traversal - Iterative and Recursive