Skip to content

Instantly share code, notes, and snippets.

@meghakrishnamurthy
Created July 5, 2016 00:54
Show Gist options
  • Save meghakrishnamurthy/e6915cd4b365cc4b013fadbdc7176809 to your computer and use it in GitHub Desktop.
Save meghakrishnamurthy/e6915cd4b365cc4b013fadbdc7176809 to your computer and use it in GitHub Desktop.
Java implementation of mirroring Binary Tree
package megha.codingproblem.trees;
/**
* Git Repo link: https://github.com/meghakrishnamurthy/CodingProblems/blob/master/src/megha/codingproblem/trees/MirrorBinaryTree.java
*
* Class to perform mirroring of a binary tree
* Time Complexity - O(n)
* Space Complexity:
* O(h) where h is the height of the binary tree
* Best/average case - O(logn)
* Worst case - O(n)
*
* @author megha krishnamurthy
*/
public class MirrorBinaryTree {
/**
* Recursive implmentation of mirroring a binary tree
* @param root
*/
public void mirror(Node node) {
if(node == null) {
return;
}
mirror(node.left);
mirror(node.right);
Node temp;
temp = node.left;
node.left = node.right;
node.right = temp;
}
/*
* Method to perform inorder traversal of a binary tree
*/
private void inOrder(Node node) {
if(node == null) {
return;
}
inOrder(node.left);
System.out.print(node.data + " ");
inOrder(node.right);
}
public static void main(String args[]) {
Node root = new Node(10);
root.left = new Node(6);
root.right = new Node(21);
root.left.left = new Node(1);
root.left.right = new Node(8);
root.right.left = new Node(13);
root.right.right = new Node(25);
root.right.left.left = new Node (12);
root.right.left.right = new Node(18);
MirrorBinaryTree mirrorTree = new MirrorBinaryTree();
mirrorTree.inOrder(root);
System.out.println();
mirrorTree.mirror(root);
mirrorTree.inOrder(root);
System.out.println();
}
}
private class Node {
int data;
Node left;
Node right;
private Node(int value) {
data = value;
left = right = null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment