How to invert a binary tree

An inversion, or mirror, of a Binary Tree (T),​ is just a Binary Tree M(T) whose left and right children (of all non-leaf nodes) are swapped.

svg viewer

Algorithm

The solution is a simple recursive approach:

  • Call invert for left-subtree.
  • Call invert for right-subtree.
  • Swap left and right subtrees.

Code

The code snippet below implements the algorithm above:

#include <iostream>
using namespace std;
/* A node contains the value, left and right pointers */
struct Node
{
int data;
struct Node* left;
struct Node* right;
};
/* Creates a new node */
struct Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
void invert(struct Node* node)
{
if (node == NULL)
return;
else
{
struct Node* temp;
/* recursive calls */
invert(node->left);
invert(node->right);
/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}
/* print InOrder binary tree traversal.*/
void print_tree(struct Node* node)
{
if (node == NULL)
return;
print_tree(node->left);
cout << node->data << " ";
print_tree(node->right);
}
int main()
{
struct Node *root = newNode(2);
root->left = newNode(1);
root->right = newNode(4);
root->right->left = newNode(3);
root->right->right = newNode(5);
cout << "Inorder traversal of the constructed"
<< " tree is" << endl;
print_tree(root);
/* Invert the tree */
invert(root);
cout << endl;
cout << "Inorder traversal of the inverted tree"
<< " is \n";
print_tree(root);
return 0;
}
Copyright ©2024 Educative, Inc. All rights reserved