Mirror image of a binary tree
Solution 1:
Sounds like homework.
It looks very easy. Write a recursive routine that depth-first visits every node and builds the mirror tree with left and right reversed.
struct node *mirror(struct node *here) {
if (here == NULL)
return NULL;
else {
struct node *newNode = malloc (sizeof(struct node));
newNode->value = here->value;
newNode->left = mirror(here->right);
newNode->right = mirror(here->left);
return newNode;
}
}
This returns a new tree - some other answers do this in place. Depends on what your assignment asked you to do :)
Solution 2:
void swap_node(node n) {
if(n != null) {
node tmp = n.left;
n.left = n.right;
n.right = tmp;
swap_node(n.left);
swap_node(n.right);
}
}
swap_node(root);
Solution 3:
Banal solution:
for each node in tree
exchange leftchild with rightchild.
Solution 4:
Recursive and Iterative methods in JAVA: 1) Recursive:
public static TreeNode mirrorBinaryTree(TreeNode root){
if(root == null || (root.left == null && root.right == null))
return root;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
mirrorBinaryTree(root.left);
mirrorBinaryTree(root.right);
return root;
}
2) Iterative:
public static TreeNode mirrorBinaryTreeIterative(TreeNode root){
if(root == null || (root.left == null && root.right == null))
return root;
TreeNode parent = root;
Stack<TreeNode> treeStack = new Stack<TreeNode>();
treeStack.push(root);
while(!treeStack.empty()){
parent = treeStack.pop();
TreeNode temp = parent.right;
parent.right = parent.left;
parent.left = temp;
if(parent.right != null)
treeStack.push(parent.right);
if(parent.left != null)
treeStack.push(parent.left);
}
return root;
}