Write a C/C++ program to convert a binary tree into its mirror image.

Mirror of Binary tree : C program

 

We can see that right side tree is mirror of left side tree in the above figure.

In-order Traversal of left Tree :      4 2 6 5 7 1 3

In-order Traversal of right Tree :   3 1 7 5 6 2 4

Note: The sequence of in-order traversal of binary tree and in-order traversal of its mirror image would be reverse in each other.

#include<stdio.h>
#include<stdlib.h>

// data sructure for tree node
struct node {
	struct node *leftChild;
	int nodeNumber;
	struct node *rightChild;
};

typedef struct node TreeNode;
TreeNode *create(int NodeNumber);
TreeNode *ConvertTreeIntoMirror(TreeNode * node);

void inorderTravel(TreeNode * node, int indent) {
	if (node != NULL) {
		inorderTravel(node->leftChild, indent + 4);
		printf("%d ", node->nodeNumber);
		inorderTravel(node->rightChild, indent + 4);
	}

}

int main() {
	/* our example tree is like
	 1
	 / \
    2   3
   /    \
  4      5
        / \
       6   7
	 */
	// let us create tree like above

	TreeNode *RootNode = create(1);
	RootNode->leftChild = create(2);
	RootNode->rightChild = create(3);
	//for child of node 2
	RootNode->leftChild->leftChild = create(4);
	RootNode->leftChild->rightChild = create(5);

	// for child of node (5)
	RootNode->leftChild->rightChild->leftChild = create(6);
	RootNode->leftChild->rightChild->rightChild = create(7);

	printf("In order traversal of input Tree:\n");
	inorderTravel(RootNode, 4);
	printf("\n");
	// mirro function
	TreeNode *MirrorRootNode = ConvertTreeIntoMirror(RootNode);
	printf("In order traversal of Mirror Tree:\n");
	inorderTravel(MirrorRootNode, 4);

	printf("\n");
	return 0;
}

TreeNode *
create(int NodeNumber) {
	TreeNode *newNode = (TreeNode *) malloc(sizeof(TreeNode));
	newNode->nodeNumber = NodeNumber;
	newNode->leftChild = NULL;
	newNode->rightChild = NULL;
	return newNode;
}

TreeNode *
ConvertTreeIntoMirror(TreeNode * node) {
	// check for empty tree
	if (node == NULL)
		return;
	else {
		TreeNode *tmp = (TreeNode *) malloc(sizeof(TreeNode));
		tmp->nodeNumber = node->nodeNumber;
		tmp->leftChild = ConvertTreeIntoMirror(node->rightChild);
		tmp->rightChild = ConvertTreeIntoMirror(node->leftChild);
		return tmp;
	}
}

 




Related Contents to follow