Created
July 5, 2016 00:54
-
-
Save meghakrishnamurthy/e6915cd4b365cc4b013fadbdc7176809 to your computer and use it in GitHub Desktop.
Java implementation of mirroring Binary Tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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