Nicholas Workshop

Mirror A Binary Tree

Nicholas Wong -

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)

Reference