Reflection of a Binary Tree

    Reflection of binary tree means if you have a binary tree like following:

                     a                                                                                 a
                  /      \                              becomes like this                  /      \
                b         c                                                                      c        b
              /    \      /   \                                                                  /    \     /   \
            d     e    f     g                                                                g     f   e    d

                       
There are 2 approaches to this problem 1- using stack 2- recursively swap sub trees
I explain both and give Java code for second approach.

1.Using Stack
     If you have recursion, you almost always can do the same job using stack. steps to produce reflection of a binary tree is:

1- Push the node in the stack
2- Pop the node from stack and if it has childes swap them
3- Push the left child and right child after swap
4- do theses steps until stack becomes empty which means you visited all nodes

example:

stack: push 'a'

pop 'a' then swap 'b' and 'c'.

stack: push 'c'. push 'b'.

pop 'b' then swap it childes, 'e' and 'd'

stack: push 'd'. push 'e'

pop 'e' which doesn't have children so return.

pop 'd' which doesn't have children so return.

stack : only contains 'c' now

continue...

pop 'c' and swap its children.

stack: push 'g'. push 'f''

pop 'f'' which doesn't have children so return.

pop 'g' which doesn't have children so return.

stack is empty now so finish.

2- Recursive method

     For operations on binary tree most of the times using recursion is a good idea.

with recursion, reflection happens in place which means the original tree replace with reflected tree.recursion is shorter than first method.

imagine you have method called reflect(Node<E> node)

which accept Node<E> of the binary tree. we call this method in our caller method with root of binary tree.

steps are:

1-if root is empty return
2- call reflect for left sub tree
3- call reflect for right sub tree
4- swap left and right sub trees using temp variable...temp is the same type of node.

Java code:

	public void reflect(BTNode<E> v)
	{
	//if tree is empty then retun nothing
	if (v==null)
	{
	return;
	}
	else
	{
	//variable to swap left and right child
	BTNode<E> temp;
	// recursive call for left subtree
	reflect(v.getLeft());
	// recursive call for right subtree
	reflect(v.getRight());
	// swap the left and right childs
	temp = v.getLeft();
	v.setLeft(v.getRight());
	v.setRight(temp);
	}
	}

view raw reflection hosted with ❤ by GitHub

Testing:
To test operation on binary tree, the best approach in my opinion is to use Graphvis website which shows you visual output based on your input. you can write a method to traverse your tree after and before reflection and generate a  Graphvis  dot file or its accepted input data, then you can use  Graphvis  to see the output is what it is supposed to be.
I give a Java code for generating dot output to use in  Graphvis  .
output is in String format, however you can write the output to a .dot file and then load it on  Graphvis  website.

Java code for generating Graphvis .dot data:

	//recursively generate dot file for graphviz
	public String toDot (BTNode<E> node)
	{
	if (node == null)
	return "";
	String solution = toDot (node.getLeft()) + toDot(node.getRight());
	if (node.getLeft() != null)
	{
	solution += (node.element()+ "--" + node.getLeft().element() + ";\n");
	}
	if (node.getRight() != null)
	{
	solution += (node.element()+ "--" + node.getRight().element() + ";\n");
	}
	return solution;
	}

view raw reflection hosted with ❤ by GitHub

p.s: When using this generator you should add the following line before the actual data inside the curly braces to give you right visual output:    graph [ordering="out"];

p.s.s: You can also use queue instead of stack.