CareerCup

void reverse(Node *pRoot)
{
    if (NULL == pRoot)
        return;
        
    Node *ptmp = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = pTmp;
    
    reverse(pRoot->left);
    reverse(pRoot->right);

}

#include <stdio.h>
struct node
{
int v;
struct node* left;
struct node* right;
};
void createtree(struct node* root)
{
int x,y;
printf("Enter left child of %d: ",root->v);
scanf("%d",&x);
printf("Enter right child of %d: ",root->v);
scanf("%d",&y);
if(x==-999)root->left=NULL;
else {
root->left=new struct node();
root->left->v=x;
root->left->left=NULL;
root->left->right=NULL;
createtree(root->left);
}
if(y==-999)root->right=NULL;
else {
root->right=new struct node();
root->right->v=y;
root->right->left=NULL;
root->right->right=NULL;
createtree(root->right);
}
}
void display(struct node* root)
{
printf("%d ",root->v);
if(root->left!=NULL)display(root->left);
if(root->right!=NULL)display(root->right);
}
void treereverse(struct node *root)
{
if(root==NULL)return;
struct node *t=root->left;
root->left=root->right;
root->right=t;
treereverse(root->left);
treereverse(root->right);
}
int main()
{
struct node* root,*start;
root=new struct node();
start=root;
int x;
printf("Enter root: ");
scanf("%d",&x);
root->v=x;
root->left=NULL;
root->right=NULL;
createtree(root);
root=start;
printf("Before reversal: \n");
display(root);
root=start;
treereverse(root);
printf("After reversal: \n");
root=start;
display(root);
}
/*The treereverse function simply swaps the left and right child of a node. The results are displayed using pre-order traversal.*/

Node* reverse(Node *root){

Node* reverse(Node *root){
if(root == NULL)
return NULL
else
Node *ltree, *rtree;
rtree = reverse(root->right);
ltree = reverse(root->left);
root->left = rtree;
root->right = ltree;
return root;
}

loop the tree by layer with stack, and do revert for every node.

loop the tree by layer with stack, and do revert for every node.

loop the tree by layer with stack, and do revert for every node.

do a preorder traversal. So you visit each node only once. At each node , if it is not null, swap the left and right pointers.

void mirror(struct node *node){
if(node == null){
return;
}
else{
struct node * temp = node->left;
node->left = node->right;
node->right = temp;

mirror(node->left);
mirror(node->right);
}
}

Step 1: Do a pre-order traversal. and store the node values in an array.
Step 2: traverse in such a way that you store the values as the problem (kind of modified pre order).

Step 1:
void preorder (node * p){
if(root == (node*) NULL)
return;
a[i] = p-> data;
i++;
preorder(p->left_p);
preorder(p->right_p);
}


void modifiedPreorder (node * p) {
if(root == (node*) NULL)
return;
p-> data = a[i];
i++;
modifiedPreorder(p->right_p);
modifiedPreorder(p->left_p);
}

In post order traversal, swap left and right subtrees instead of visiting

visited = NULL;
do
{
	while( p != NULL )
		stack.push(p);
		p = p->left;
	
	while( !stack.empty() )
	{
		temp = stack.top();
		if( temp->right == NULL || temp->right == visited )
			stack.pop();
			swap( temp->left, temp->right ); // swap instead of visit
			visited = temp;
			continue;
	
		if( temp->right != NULL )
			p = temp->right;
			break;
	}
}while( p != NULL || !stack.empty() );

public class ReverseBinaryTree {

	public static void main(String args[]) {
		TreeNode root = new TreeNode();
		root.setData(1);
		TreeNode node1 = new TreeNode();
		node1.setData(2);
		TreeNode node2 = new TreeNode();
		node2.setData(3);
		TreeNode node3 = new TreeNode();
		node3.setData(4);
		TreeNode node4 = new TreeNode();
		node4.setData(5);
		TreeNode node5 = new TreeNode();
		node5.setData(6);
		TreeNode node6 = new TreeNode();
		node6.setData(7);
		root.setLeftNode(node1);
		root.setRightNode(node2);
		node1.setLeftNode(node3);
		node1.setRightNode(node4);
		node2.setLeftNode(node5);
		node2.setRightNode(node6);
		node3.setLeftNode(null);
		node3.setRightNode(null);
		node4.setLeftNode(null);
		node4.setRightNode(null);
		node5.setLeftNode(null);
		node5.setRightNode(null);
		node6.setLeftNode(null);
		node6.setRightNode(null);

		preorderTraversal(root);

		reverseTree(root);

		preorderTraversal(root);
	}

	public static void preorderTraversal(TreeNode root) {
		if (root != null) {
			System.out.println(root.getData());
			preorderTraversal(root.getLeftNode());
			preorderTraversal(root.getRightNode());
		}
	}

	public static void reverseTree(TreeNode node) {
		if (node != null) {
			swap(node);
			reverseTree(node.getLeftNode());
			reverseTree(node.getRightNode());
		}

	}

	public static void swap(TreeNode node) {
		if (node.getLeftNode() != null && node.getRightNode() != null) {
			TreeNode temp = node.getLeftNode();
			node.setLeftNode(node.getRightNode());
			node.setRightNode(temp);
		}
	}

}