Mirror A 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 Node:
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 mirror_tree(node):
if not node: return
visit(node)
if node.left: mirror_tree(node.left)
if node.right: mirror_tree(node.right)
def print_tree(node):
this_level = [node]
while this_level:
next_level = list()
print map(lambda n: n.value, this_level)
for n in this_level:
if n.left: next_level.append(n.left)
if n.right: next_level.append(n.right)
this_level = next_level
# a binary tree and display how was it before reflection
print 'original'
node_05 = Node(5)
node_07 = Node(7)
node_09 = Node(9)
node_11 = Node(11)
node_06 = Node(6, node_05, node_07)
node_10 = Node(10, node_09, node_11)
node_08 = Node(8, node_06, node_10)
root = node_08
print_tree(root)
# do reflection
print ''
print 'became'
mirror_tree(root)
print_tree(root)
