Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

invert
tree
binary

How to invert a binary tree

Educative Answers Team

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; 
} 

RELATED TAGS

invert
tree
binary
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring