Tuesday, 30 June 2015

Mirror a Binary tree


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