Create a mirror tree from the given binary tree - GeeksforGeeks (2024)

Last Updated : 26 Mar, 2023

Summarize

Comments

Improve

Given a binary tree, the task is to create a new binary tree which is a mirror image of the given binary tree.

Examples:

Input: 5 / \ 3 6 / \ 2 4Output:Inorder of original tree: 2 3 4 5 6 Inorder of mirror tree: 6 5 4 3 2Mirror tree will be: 5 / \6 3 / \ 4 2Input: 2 / \ 1 8 / \ 12 9Output:Inorder of original tree: 12 1 2 8 9 Inorder of mirror tree: 9 8 2 1 12

Approach: Write a recursive function that will take two nodes as the argument, one of the original tree and the other of the newly created tree. Now, for every passed node of the original tree, create a corresponding node in the mirror tree and then recursively call the same method for the child nodes but passing the left child of the original tree node with the right child of the mirror tree node and the right child of the original tree node with the left child of the mirror tree node.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach

#include <iostream>

using namespace std;

// A binary tree node has data, pointer to

// left child and a pointer to right child

typedef struct treenode {

int val;

struct treenode* left;

struct treenode* right;

} node;

// Helper function that allocates a new node with the

// given data and NULL left and right pointers

node* createNode(int val)

{

node* newNode = (node*)malloc(sizeof(node));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

// Helper function to print Inorder traversal

void inorder(node* root)

{

if (root == NULL)

return;

inorder(root->left);

cout <<" "<< root->val;

inorder(root->right);

}

// mirrorify function takes two trees,

// original tree and a mirror tree

// It recurses on both the trees,

// but when original tree recurses on left,

// mirror tree recurses on right and

// vice-versa

void mirrorify(node* root, node** mirror)

{

if (root == NULL) {

mirror = NULL;

return;

}

// Create new mirror node from original tree node

*mirror = createNode(root->val);

mirrorify(root->left, &((*mirror)->right));

mirrorify(root->right, &((*mirror)->left));

}

// Driver code

int main()

{

node* tree = createNode(5);

tree->left = createNode(3);

tree->right = createNode(6);

tree->left->left = createNode(2);

tree->left->right = createNode(4);

// Print inorder traversal of the input tree

cout <<"Inorder of original tree: ";

inorder(tree);

node* mirror = NULL;

mirrorify(tree, &mirror);

// Print inorder traversal of the mirror tree

cout <<"\nInorder of mirror tree: ";

inorder(mirror);

return 0;

}

// This code is contributed by shivanisinghss2110

C

// C implementation of the approach

#include <malloc.h>

#include <stdio.h>

// A binary tree node has data, pointer to

// left child and a pointer to right child

typedef struct treenode {

int val;

struct treenode* left;

struct treenode* right;

} node;

// Helper function that allocates a new node with the

// given data and NULL left and right pointers

node* createNode(int val)

{

node* newNode = (node*)malloc(sizeof(node));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

// Helper function to print Inorder traversal

void inorder(node* root)

{

if (root == NULL)

return;

inorder(root->left);

printf("%d ", root->val);

inorder(root->right);

}

// mirrorify function takes two trees,

// original tree and a mirror tree

// It recurses on both the trees,

// but when original tree recurses on left,

// mirror tree recurses on right and

// vice-versa

void mirrorify(node* root, node** mirror)

{

if (root == NULL) {

mirror = NULL;

return;

}

// Create new mirror node from original tree node

*mirror = createNode(root->val);

mirrorify(root->left, &((*mirror)->right));

mirrorify(root->right, &((*mirror)->left));

}

// Driver code

int main()

{

node* tree = createNode(5);

tree->left = createNode(3);

tree->right = createNode(6);

tree->left->left = createNode(2);

tree->left->right = createNode(4);

// Print inorder traversal of the input tree

printf("Inorder of original tree: ");

inorder(tree);

node* mirror = NULL;

mirrorify(tree, &mirror);

// Print inorder traversal of the mirror tree

printf("\nInorder of mirror tree: ");

inorder(mirror);

return 0;

}

Java

// Java implementation of the approach

import java.util.Comparator;

class GFG

{

// A binary tree node has data, pointer to

// left child and a pointer to right child

static class node

{

int val;

node left;

node right;

}

// Helper function that allocates

// a new node with the given data

// and null left and right pointers

static node createNode(int val)

{

node newNode = new node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Helper function to print Inorder traversal

static void inorder(node root)

{

if (root == null)

return;

inorder(root.left);

System.out.print(root.val);

inorder(root.right);

}

// mirrorify function takes two trees,

// original tree and a mirror tree

// It recurses on both the trees,

// but when original tree recurses on left,

// mirror tree recurses on right and

// vice-versa

static node mirrorify(node root)

{

if (root == null)

{

return null;

}

// Create new mirror node from original tree node

node mirror = createNode(root.val);

mirror.right = mirrorify(root.left);

mirror.left = mirrorify(root.right);

return mirror;

}

// Driver code

public static void main(String args[])

{

node tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

// Print inorder traversal of the input tree

System.out.print("Inorder of original tree: ");

inorder(tree);

node mirror = null;

mirror = mirrorify(tree);

// Print inorder traversal of the mirror tree

System.out.print("\nInorder of mirror tree: ");

inorder(mirror);

}

}

// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of the approach

# A binary tree node has data,

# pointer to left child and

# a pointer to right child

# Linked list node

class Node:

def __init__(self, data):

self.data = data

self.left = None

self.right = None

# Helper function that allocates

# a new node with the given data

# and None left and right pointers

def createNode(val):

newNode = Node(0)

newNode.val = val

newNode.left = None

newNode.right = None

return newNode

# Helper function to print Inorder traversal

def inorder(root):

if (root == None):

return

inorder(root.left)

print( root.val, end = " ")

inorder(root.right)

# mirrorify function takes two trees,

# original tree and a mirror tree

# It recurses on both the trees,

# but when original tree recurses on left,

# mirror tree recurses on right and

# vice-versa

def mirrorify(root, mirror):

if (root == None) :

mirror = None

return mirror

# Create new mirror node

# from original tree node

mirror = createNode(root.val)

mirror.right = mirrorify(root.left,

((mirror).right))

mirror.left = mirrorify(root.right,

((mirror).left))

return mirror

# Driver Code

if __name__=='__main__':

tree = createNode(5)

tree.left = createNode(3)

tree.right = createNode(6)

tree.left.left = createNode(2)

tree.left.right = createNode(4)

# Print inorder traversal of the input tree

print("Inorder of original tree: ")

inorder(tree)

mirror = None

mirror = mirrorify(tree, mirror)

# Print inorder traversal of the mirror tree

print("\nInorder of mirror tree: ")

inorder(mirror)

# This code is contributed by Arnab Kundu

C#

// c# implementation of the approach

using System;

public class GFG

{

// A binary tree node has data, pointer to

// left child and a pointer to right child

public class node

{

public int val;

public node left;

public node right;

}

// Helper function that allocates

// a new node with the given data

// and null left and right pointers

public static node createNode(int val)

{

node newNode = new node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Helper function to print Inorder traversal

public static void inorder(node root)

{

if (root == null)

{

return;

}

inorder(root.left);

Console.Write("{0:D} ", root.val);

inorder(root.right);

}

// mirrorify function takes two trees,

// original tree and a mirror tree

// It recurses on both the trees,

// but when original tree recurses on left,

// mirror tree recurses on right and

// vice-versa

public static node mirrorify(node root)

{

if (root == null)

{

return null;

}

// Create new mirror node from original tree node

node mirror = createNode(root.val);

mirror.right = mirrorify(root.left);

mirror.left = mirrorify(root.right);

return mirror;

}

// Driver code

public static void Main(string[] args)

{

node tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

// Print inorder traversal of the input tree

Console.Write("Inorder of original tree: ");

inorder(tree);

node mirror = null;

mirror = mirrorify(tree);

// Print inorder traversal of the mirror tree

Console.Write("\nInorder of mirror tree: ");

inorder(mirror);

}

}

Javascript

<script>

// Javascript implementation of the approach

// A binary tree node has data, pointer to

// left child and a pointer to right child

class node

{

constructor()

{

this.val=0;

this.left=this.right=null;

}

}

// Helper function that allocates

// a new node with the given data

// and null left and right pointers

function createNode(val)

{

let newNode = new node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Helper function to print Inorder traversal

function inorder(root)

{

if (root == null)

return;

inorder(root.left);

document.write(root.val+" ");

inorder(root.right);

}

// mirrorify function takes two trees,

// original tree and a mirror tree

// It recurses on both the trees,

// but when original tree recurses on left,

// mirror tree recurses on right and

// vice-versa

function mirrorify(root)

{

if (root == null)

{

return null;

}

// Create new mirror node from original tree node

let mirror = createNode(root.val);

mirror.right = mirrorify(root.left);

mirror.left = mirrorify(root.right);

return mirror;

}

// Driver code

let tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

// Print inorder traversal of the input tree

document.write("Inorder of original tree: ");

inorder(tree);

let mirror = null;

mirror = mirrorify(tree);

// Print inorder traversal of the mirror tree

document.write("<br>Inorder of mirror tree: ");

inorder(mirror);

// This code is contributed by avanitrachhadiya2155

</script>

Output

Inorder of original tree: 2 3 4 5 6 Inorder of mirror tree: 6 5 4 3 2 

Time Complexity: O(n), where n is the number of nodes in the tree. This is because we need to visit each node in the tree exactly once to swap its left and right child nodes.
Auxiliary Space: O(h), where h is the height of the binary tree. This is because the maximum amount of space used by the algorithm at any given time is the size of the call stack, which is at most equal to the height of the binary tree. This is because each recursive call to mirror adds a new frame to the call stack, and the stack grows to a maximum depth of the height of the tree. Therefore, the space used by the algorithm is proportional to the height of the tree.

Approach 2:
In order to change the original tree in its mirror tree, then we simply swap the left and right link of each node. If the node is leaf node then do nothing.

C++

#include <iostream>

using namespace std;

typedef struct treenode {

int val;

struct treenode* left;

struct treenode* right;

} node;

// Helper function that

// allocates a new node with the

// given data and NULL left and right pointers

node* createNode(int val)

{

node* newNode = (node*)malloc(sizeof(node));

newNode->val = val;

newNode->left = NULL;

newNode->right = NULL;

return newNode;

}

// Function to print the inrder traversal

void inorder(node* root)

{

if (root == NULL)

return;

inorder(root->left);

printf("%d ", root->val);

inorder(root->right);

}

// Function to convert to mirror tree

treenode* mirrorTree(node* root)

{

// Base Case

if (root == NULL)

return root;

node* t = root->left;

root->left = root->right;

root->right = t;

if (root->left)

mirrorTree(root->left);

if (root->right)

mirrorTree(root->right);

return root;

}

// Driver Code

int main()

{

node* tree = createNode(5);

tree->left = createNode(3);

tree->right = createNode(6);

tree->left->left = createNode(2);

tree->left->right = createNode(4);

printf("Inorder of original tree: ");

inorder(tree);

// Function call

mirrorTree(tree);

printf("\nInorder of Mirror tree: ");

inorder(tree);

return 0;

}

Java

import java.util.*;

class GFG{

static class Node

{

int val;

Node left;

Node right;

}

// Helper function that allocates

// a new node with the given data

// and null left and right references

public static Node createNode(int val)

{

Node newNode = new Node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Function to print the inorder traversal

public static void inOrder(Node root)

{

if (root == null)

return;

inOrder(root.left);

System.out.print(root.val + " ");

inOrder(root.right);

}

// Function to convert to mirror tree

// by swapping the left and right links.

public static Node mirrorTree(Node root)

{

if (root == null)

return null;

Node left = mirrorTree(root.left);

Node right = mirrorTree(root.right);

root.left = right;

root.right = left;

return root;

}

// Driver Code

public static void main(String args[])

{

Node tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

System.out.print("Inorder of original tree: ");

inOrder(tree);

// Function call

mirrorTree(tree);

System.out.print("\nInorder of mirror tree: ");

inOrder(tree);

}

}

// This code is contributed by Ryan Ranaut

Python3

# code

class Node:

def __init__(self,data):

self.left = None

self.right = None

self.data = data

def inOrder(root):

if root is not None:

inOrder(root.left)

print (root.data, end = ' ')

inOrder(root.right)

#we recursively call the mirror function which swaps the right subtree with the left subtree.

def mirror(root):

if root is None:

return

mirror(root.left)

mirror(root.right)

root.left, root.right = root.right, root.left

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.right.left = Node(5)

print("The inorder traversal of the tree before mirroring:",end=' ')

print(inOrder(root))

# 4 2 1 5 3

print()

mirror(root)

print("The inorder traversal of the tree after mirroring:",end=' ')

print(inOrder(root))

# 3 5 1 2 4

C#

using System;

public class GFG{

public class Node

{

public int val;

public Node left;

public Node right;

}

// Helper function that allocates

// a new node with the given data

// and null left and right references

public static Node createNode(int val)

{

Node newNode = new Node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Function to print the inorder traversal

public static void inOrder(Node root)

{

if (root == null)

return;

inOrder(root.left);

Console.Write(root.val + " ");

inOrder(root.right);

}

// Function to convert to mirror tree

// by swapping the left and right links.

public static Node mirrorTree(Node root)

{

if (root == null)

return null;

Node left = mirrorTree(root.left);

Node right = mirrorTree(root.right);

root.left = right;

root.right = left;

return root;

}

// Driver Code

public static void Main(String []args)

{

Node tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

Console.Write("Inorder of original tree: ");

inOrder(tree);

// Function call

mirrorTree(tree);

Console.Write("\nInorder of mirror tree: ");

inOrder(tree);

}

}

// This code is contributed by shivanisinghss2110

Javascript

<script>

class Node

{

constructor()

{

this.val=0;

this.left=this.right=null;

}

}

// Helper function that allocates

// a new node with the given data

// and null left and right references

function createNode(val)

{

let newNode = new Node();

newNode.val = val;

newNode.left = null;

newNode.right = null;

return newNode;

}

// Function to print the inorder traversal

function inOrder(root)

{

if (root == null)

return;

inOrder(root.left);

document.write(root.val + " ");

inOrder(root.right);

}

// Function to convert to mirror tree

// by swapping the left and right links.

function mirrorTree(root)

{

if (root == null)

return null;

let left = mirrorTree(root.left);

let right = mirrorTree(root.right);

root.left = right;

root.right = left;

return root;

}

// Driver Code

let tree = createNode(5);

tree.left = createNode(3);

tree.right = createNode(6);

tree.left.left = createNode(2);

tree.left.right = createNode(4);

document.write("Inorder of original tree: " );

inOrder(tree);

// Function call

mirrorTree(tree);

document.write("<br>" +"\nInorder of mirror tree: ");

inOrder(tree);

// This code is contributed by shivanisinghss2110

</script>

Output

Inorder of original tree: 2 3 4 5 6 Inorder of Mirror tree: 6 5 4 3 2 

Time complexity: O(N) where N is the number of nodes in given binary tree.
Auxiliary Space: O(h) where h is the height of the tree. due to recursion call stack.



anindyapal007

Create a mirror tree from the given binary tree - GeeksforGeeks (2)

Improve

Next Article

Check whether the two Binary Search Trees are Identical or Not

Create a mirror tree from the given binary tree - GeeksforGeeks (2024)
Top Articles
Latest Posts
Recommended Articles
Article information

Author: Terrell Hackett

Last Updated:

Views: 5609

Rating: 4.1 / 5 (72 voted)

Reviews: 95% of readers found this page helpful

Author information

Name: Terrell Hackett

Birthday: 1992-03-17

Address: Suite 453 459 Gibson Squares, East Adriane, AK 71925-5692

Phone: +21811810803470

Job: Chief Representative

Hobby: Board games, Rock climbing, Ghost hunting, Origami, Kabaddi, Mushroom hunting, Gaming

Introduction: My name is Terrell Hackett, I am a gleaming, brainy, courageous, helpful, healthy, cooperative, graceful person who loves writing and wants to share my knowledge and understanding with you.