Convert a binary tree to its mirror tree

Given a tree, convert the tree to its corresponding mirror tree.
A mirror tree of a tree is where left node of the root of the tree is right node of the mirror tree and right node of the tree is left node of mirror tree and left and right subtrees of the root are also mirror trees.
Example 1:
Tree:
                1
        2                3
    4                5        

Mirror Tree:
                1
        3                2
            5                4


Video coming soon!



Subscribe for more updates


Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Boundary condition: If root is null, then return.
Recursive step: Recursively convert left and right sub trees to their mirror.
Actual conversion to mirror: Swap left and right sub trees of the current node.
Please checkout code snippet and algorithm visualization section for understanding the algorithm.


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh.mirrortree;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Transform a tree to its mirror tree
 *
 * @author Saurabh
 */
public class MirrorTree {
	
	private TreeNode root;
	
	public void convertToMirror() {
		convertToMirror(root);
	}
	
	private void convertToMirror(TreeNode root) {
		if(root == null) {
			return;
		}
		// Mirror left subtree
		convertToMirror(root.getLeft());
		// Mirror right subtree
		convertToMirror(root.getRight());
		
		// Interchange left and right subtree root nodes
		TreeNode t = root.getLeft();
		root.setLeft(root.getRight());
		root.setRight(t);		
	}
	
	/*
	 * Create a sample tree
	 * 				  1
	 * 			2			3
	 * 		4			5		
	 * 
	 */
	public void createSampleTree() {
		root = new TreeNode(1, new TreeNode(2, new TreeNode(4), null), new TreeNode(3, new TreeNode(5), null));		
	}
	
	public void inorder() {
		inorder(root);
		System.out.println();
	}
	
	private void inorder(TreeNode root) {
		if(root == null) {
			return;
		}
		inorder(root.getLeft());
		System.out.print(root.getData() + " ");
		inorder(root.getRight());
	}
	
	public static void main(String[] args) {
		MirrorTree tree = new MirrorTree();
		tree.createSampleTree();
		tree.inorder();
		tree.convertToMirror();
		tree.inorder();
	}
}

class TreeNode {
	
	private int data;
	private TreeNode left;
	private TreeNode right;
	
	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public TreeNode getLeft() {
		return left;
	}

	public void setLeft(TreeNode left) {
		this.left = left;
	}

	public TreeNode getRight() {
		return right;
	}

	public void setRight(TreeNode right) {
		this.right = right;
	}

	public TreeNode(int data) {
		this.data = data;
	}
	
	public TreeNode(int data, TreeNode left, TreeNode right) {
		this.data = data;
		this.left = left;
		this.right = right;
	}	
}
		

Order of the Algorithm

Time Complexity is O(n) since all nodes of both trees are visited in the worst case.
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer