js

Saturday, August 27, 2022

Invert/Mirror binary tree

 

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. 
 

MirrorTree1

Trees in the above figure are mirror of each other


Method 1 (Recursive)

Algorithm – Mirror(tree): 

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

Implementation:

// C++ program to convert a binary tree
// to its mirror
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer 
to left child and a pointer to right child */
struct Node 
{
    int data;
    struct Node* left;
    struct Node* right;
};
  
/* Helper function that allocates a new node with 
the given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*)
                         malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
      
    return(node);
}
  
  
/* Change a tree so that the roles of the left and 
    right pointers are swapped at every node.
  
So the tree...
    4
    / \
    2 5
    / \
1 3
  
is changed to...
    4
    / \
    5 2
        / \
    3 1
*/
void mirror(struct Node* node) 
{
    if (node == NULL) 
        return; 
    else
    {
        struct Node* temp;
          
        /* do the subtrees */
        mirror(node->left);
        mirror(node->right);
      
        /* swap the pointers in this node */
        temp     = node->left;
        node->left = node->right;
        node->right = temp;
    }
} 
  
/* Helper function to print 
Inorder traversal.*/
void inOrder(struct Node* node) 
{
    if (node == NULL) 
        return;
      
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
} 
  
  
// Driver Code
int main()
{
    struct Node *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 */
    cout << "Inorder traversal of the constructed"
         << " tree is" << endl;
    inOrder(root);
      
    /* Convert tree to its mirror */
    mirror(root); 
      
    /* Print inorder traversal of the mirror tree */
    cout << "\nInorder traversal of the mirror tree"
         << " is \n"; 
    inOrder(root);
      
    return 0; 
}
  
// This code is contributed by Akanksha Rai

Output:  

Inorder traversal of the constructed tree is 
4 2 5 1 3 
Inorder traversal of the mirror tree is 
3 1 5 2 4 

Time & Space Complexities: Worst-case Time complexity is O(n) and for space complexity, If we don’t consider the size of the recursive stack for function calls then O(1) otherwise O(h) where h is the height of the tree.  This program is similar to traversal of tree space and time complexities will be the same as Tree traversal more for information Please see our Tree Traversal post for details.

Method 2 (Iterative): The idea is to do queue based level order traversal. While doing traversal, swap left and right children of every node.
Implementation:

// Iterative CPP program to convert a Binary
// Tree to its mirror
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to
   left child and a pointer to right child */
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};
  
/* Helper function that allocates a new node
   with the given data and NULL left and right
   pointers. */
struct Node* newNode(int data)
  
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return(node);
}
  
/* Change a tree so that the roles of the  left and
    right pointers are swapped at every node.
 So the tree...
       4
      / \
     2   5
    / \
   1   3
  
 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(Node* root)
{
    if (root == NULL)
        return;
  
    queue<Node*> q;
    q.push(root);
  
    // Do BFS. While doing BFS, keep swapping
    // left and right children
    while (!q.empty())
    {
        // pop top node from queue
        Node* curr = q.front();
        q.pop();
  
        // swap left child with right child
        swap(curr->left, curr->right);
  
        // push left and right children
        if (curr->left)
            q.push(curr->left);
        if (curr->right)
            q.push(curr->right);
    }
}
  
  
/* Helper function to print Inorder traversal.*/
void inOrder(struct Node* node)
{
    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
}
  
  
/* Driver program to test mirror() */
int main()
{
    struct Node *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 */
    cout << "\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 */
    cout << "\n Inorder traversal of the "
           "mirror tree is \n";
    inOrder(root);
  
    return 0;
}

Output: 

 Inorder traversal of the constructed tree is 
4 2 5 1 3 
 Inorder traversal of the mirror tree is 
3 1 5 2 4 

No comments:

Post a Comment

  Write a Program to Find the Maximum Depth or Height of a Tree Difficulty Level : Easy Last Updated : 21 Jul, 2022 Read Discuss Given ...