How would you mirror a Binary tree?

Mirroring a binary tree is a problem asked in a lot of interviews and we will be tackling it in a simple but efficient manner.
Any tree related problem should be attempted to be solved in a recursive approach since Tree is a localized data structure i.e small trees make up large trees. Here in this example we will take a case of Binary Search Tree being mirrored. This serves two purposes. The tree gets mirrored and when you print it inorder it gets sorted in the other way. Ascending if it was descending and vice versa.
We will use our very popular TreeNode class definition for this example.

static TreeNode mirrorTree(TreeNode node){
  if (node == null)
    return node;
  TreeNode left = mirrorTree(node.left);
  TreeNode right= mirrorTree(node.right);
  node.left=right;
  node.right=left;
  return node;
}

Testing code as follows.

public class BSTUtil {
 public static void main(String[] args) {
	TreeNode root=new TreeNode(8);
	TreeNode.insert(root, new TreeNode(31));
	TreeNode.insert(root, new TreeNode(45));
	TreeNode.insert(root, new TreeNode(16));
	TreeNode.insert(root, new TreeNode(24));
	TreeNode.insert(root, new TreeNode(19));
	TreeNode.insert(root, new TreeNode(29));
	TreeNode.insert(root, new TreeNode(7));
	
	StringBuffer inorderbuf=new StringBuffer();
	TreeNode.getInorder(root, inorderbuf);
	System.out.println("In order tree before mirroring"+inorderbuf);
	
	mirrorTree(root);
	
	inorderbuf=new StringBuffer();
	TreeNode.getInorder(root, inorderbuf);
	System.out.println("In order tree after mirroring "+inorderbuf);
 }
}

Output will be like

In order tree before mirroring 7 8 16 19 24 29 31 45
In order tree after mirroring 45 31 29 24 19 16 8 7

 

core java 12

FOLLOW US ON LinkedIn



Explore Tutu'rself