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.
The solution is a simple recursive approach:
invert
for left-subtree.invert
for right-subtree.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; }
RELATED TAGS
View all Courses