Mirror a binary tree works by recursing in post order , and then swapping left and right pointers of the node
#include<stdio.h>
#include<stdlib.h>
struct treeNode
{
int data;
struct treeNode* left;
struct treeNode* right;
};
struct treeNode* newNode(int n)
{
struct treeNode* node = (struct treeNode*) malloc(sizeof(struct treeNode));
node->data = n;
node->left = NULL;
node->right = NULL;
return node;
}
void mirror(struct treeNode* node)
{
if (node == NULL)
return;
//go to left node
mirror(node->left);
mirror(node->right);
//swap left and right node child pointers
struct treeNode* temp = node->left;
node->left = node->right;
node -> right = temp;
}
void inOrder(struct treeNode* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->data);
inOrder(node->right);
}
int main()
{
struct treeNode *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);
/* Convert tree to its mirror */
mirror(root);
/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);
getchar();
return 0;
}
No comments:
Post a Comment