## Interview Practice 15 – Mirror Image of Binary Tree

### Question

Construct 2 algorithms to make mirror image of any binary tree inputs, one of them using recursive method, another one using looping method. Mirror image means a binary tree that is the horizontal reflection of the original tree.

### Solution

First, to do it in recursive method, we can perform pre-order traversal as usual, see preference. Then swap the left and right children for every node.

```reflect(node)
if node is null then return
swap(node.left, node.right)
if node.left is not null then reflect(node.left)
if node.right is not null then reflect(node.right)```

Second, to do it in looping method, we can make use of a stack. Put root node in the stack first. Then in a while-loop, as long as the stack isn’t empty, swap its children. Then put the children nodes into the stack.

```reflect(root)
if root is null then return
stack.push(root)
while stack is not empty, do
node = stack.pop()
swap(node.left, node.right)
if node.left is not null then reflect(node.left)
if node.right is not null then reflect(node.right)```

### Example

```# node structure
class bst_node:
value = None
left = None
right = None
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

# swap node's children while visiting
def visit(node):
temp = node.left
node.left = node.right
node.right = temp

# reflect a binary tree
def depth_first_traversal(node):
if not node: return
visit(node)
if node.left: depth_first_traversal(node.left)
if node.right: depth_first_traversal(node.right)

# debug function to print tree
def print_tree(node, indent=''):
print "%s-%s" % (indent, node.value)
if node.left: print_tree(node.left, indent + '  ')
if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)```
```# node structure
class bst_node:
value = None
left = None
right = None
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

# what to do in a loop, here swap the children
def visit(node):
temp = node.left
node.left = node.right
node.right = temp

# reflect a binary tree
def depth_first_traversal(root):
if not root: return
stack = [root]
while len(stack) > 0:
node = stack.pop()
visit(node)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)

# debug function to print tree
def print_tree(node, indent=''):
print "%s-%s" % (indent, node.value)
if node.left: print_tree(node.left, indent + '  ')
if node.right: print_tree(node.right, indent + '  ')

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)
root = node_08
print_tree(root)

# do reflection
depth_first_traversal(root)
print_tree(root)```
```struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
//就是递归翻转树，有子树则递归翻转子树。
//July、2010/10/19

void Revertsetree(list *root)
{
if(!root)
return;
list *p;

p=root->leftch;
root->leftch=root->rightch;
root->rightch=p;

if(root->leftch)
Revertsetree(root->leftch);
if(root->rightch)
Revertsetree(root->rightch);
}```
```void Revertsetree(list *phead)
{
return;

stack<list*> stacklist;

while(stacklist.size())
//在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树
{
list* pnode=stacklist.top();
stacklist.pop();

list *ptemp;
ptemp=pnode->leftch;
pnode->leftch=pnode->rightch;
pnode->rightch=ptemp;

if(pnode->leftch)
stacklist.push(pnode->leftch);   //若有左子树，把它的左子树压入栈中
if(pnode->rightch)
stacklist.push(pnode->rightch);  //若有右子树，把它的右子树压入栈中
}
}```

### Reference

Pre-order Tree Transversal (Wikipedia)