Swapping left and right subtrees

An elegant method of swapping the left and right subtrees of a given binary tree makes use of a recursive algorithm, which recursively swaps the left and right subtrees, starting from the root.

Example

#include <stdio.h>
#include <stdlib.h>
struct tnode {
	int data;
	struct tnode *lchild, *rchild;
};

struct tnode *insert(struct tnode *p, int val) {
	struct tnode *temp1, *temp2;
	if (p == NULL) {
		p = (struct tnode *) malloc(sizeof(struct tnode));
                /* insert the new node as root node*/
		if (p == NULL) {
			printf("Cannot allocate\n");
			exit(0);
		}
		p->data = val;
		p->lchild = p->rchild = NULL;
	} else {
		temp1 = p;
		/* traverse the tree to get a pointer to that node
                 whose child will be the newly created node*/
		while (temp1 != NULL) {
			temp2 = temp1;
			if (temp1->data > val)
				temp1 = temp1->lchild;
			else
				temp1 = temp1->rchild;
		}
		if (temp2->data > val) {
			temp2->lchild = (struct tnode*) malloc(sizeof(struct tnode));
			/ *inserts the newly created node
			as left child*/
			temp2 = temp2->lchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		} else {
			temp2->rchild = (struct tnode*) malloc(sizeof(struct tnode));
			/ *inserts the newly created node
			as left child*/
			temp2 = temp2->rchild;
			if (temp2 == NULL) {
				printf("Cannot allocate\n");
				exit(0);
			}
			temp2->data = val;
			temp2->lchild = temp2->rchild = NULL;
		}
	}
	return (p);
}
/* a function to binary tree in inorder */
void inorder(struct tnode *p) {
	if (p != NULL) {
		inorder(p->lchild);
		printf("%d\t", p->data);
		inorder(p->rchild);
	}
}
struct tnode *swaptree(struct tnode *p) {
	struct tnode *temp1 = NULL, *temp2 = NULL;
	if (p != NULL) {
		temp1 = swaptree(p->lchild);
		temp2 = swaptree(p->rchild);
		p->rchild = temp1;
		p->lchild = temp2;
	}
	return (p);
}

int main() {
	struct tnode *root = NULL;
	int n, x;
	printf("Enter the number of nodes\n");
	scanf("%d", &n);
	while (n - > 0)
	{
		printf("Enter the data value\n");
		scanf("%d", &x);
		root = insert(root, x);
	}
	printf("The created tree is :\n");
	inorder(root);
	printf("The tree after swapping is :\n");
	root = swaptree(root);
	inorder(root);
	printf("\nThe original tree is \n");
	root = swaptree(root);
	inorder(root);
	getchar();
	return 0;
}

Explanation

Input:

1. The number of nodes that the tree to be created should have
2. The data values of each node in the tree to be created.

Output:

1. The data value of the nodes of the tree in inorder before interchanging the left and right subtrees
2. The data value of the nodes of the tree in inorder after interchanging the left and right subtrees

Example

1. The number of nodes that the created tree should have = 5
2. The data values of the nodes in the tree to be created are: 10, 20, 5, 9, 8

Output:
1. 5 8 9 10 20
2. 20 10 9 8 5