Python Program to Create a Mirror Copy of a Tree and Display using BFS Traversal

This is a Python program to create a mirror copy of a binary tree and display its BFS traversal.

Problem Description

The program creates a mirror copy of a binary tree and displays its BFS traversal.

Problem Solution

1. Create a class BinaryTree with instance variables key, left and right.
2. Define methods set_root, insert_left, insert_right, mirror_copy, bfs and search.
3. The method set_root takes a key as argument and sets the variable key equal to it.
4. The methods insert_left and insert_right insert a node as the left and right child respectively.
5. The method bfs displays the BFS traversal.
6. The method search returns a node with a specified key.
7. The method mirror_copy returns a mirror copy of the tree.

Program/Source Code

Here is the source code of a Python program to create a mirror copy of a tree and display its BFS traversal. The program output is shown below.

class BinaryTree:
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
 
    def set_root(self, key):
        self.key = key
 
    def insert_left(self, new_node):
        self.left = new_node
 
    def insert_right(self, new_node):
        self.right = new_node
 
    def search(self, key):
        if self.key == key:
            return self
        if self.left is not None:
            temp =  self.left.search(key)
            if temp is not None:
                return temp
        if self.right is not None:
            temp =  self.right.search(key)
            return temp
        return None
 
    def mirror_copy(self):
        mirror = BinaryTree(self.key)
        if self.right is not None:
            mirror.left = self.right.mirror_copy()
        if self.left is not None:
            mirror.right = self.left.mirror_copy()
        return mirror
 
    def bfs(self):
        queue = [self]
        while queue != []:
            popped = queue.pop(0)
            if popped.left is not None:
                queue.append(popped.left)
            if popped.right is not None:
                queue.append(popped.right)
            print(popped.key, end=' ')
 
 
btree = None
 
print('Menu (this assumes no duplicate keys)')
print('insert <data> at root')
print('insert <data> left of <data>')
print('insert <data> right of <data>')
print('mirror')
print('quit')
 
while True:
    do = input('What would you like to do? ').split()
 
    operation = do[0].strip().lower()
    if operation == 'insert':
        data = int(do[1])
        new_node = BinaryTree(data)
        suboperation = do[2].strip().lower() 
        if suboperation == 'at':
                btree = new_node
        else:
            position = do[4].strip().lower()
            key = int(position)
            ref_node = None
            if btree is not None:
                ref_node = btree.search(key)
            if ref_node is None:
                print('No such key.')
                continue
            if suboperation == 'left':
                ref_node.insert_left(new_node)
            elif suboperation == 'right':
                ref_node.insert_right(new_node)
 
    elif operation == 'mirror':
        if btree is not None:
            print('Creating mirror copy...')
            mirror = btree.mirror_copy()
            print('BFS traversal of original tree: ')
            btree.bfs()
            print()
            print('BFS traversal of mirror: ')
            mirror.bfs()
            print()
 
    elif operation == 'quit':
        break
Program Explanation

1. A variable is created to store the binary tree.
2. The user is presented with a menu to perform operations on the tree.
3. The corresponding methods are called to perform each operation.
4. The method mirror_copy is called to construct a mirror copy of the tree and then the BFS traversal of the original and the mirror copy is displayed.

advertisement
advertisement
Runtime Test Cases
Case 1:
Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
mirror
quit
What would you like to do? insert 1 at root
What would you like to do? insert 2 left of 1
What would you like to do? insert 3 right of 1
What would you like to do? insert 4 left of 2
What would you like to do? insert 5 left of 3
What would you like to do? insert 6 right of 3
What would you like to do? mirror
Creating mirror copy...
BFS traversal of original tree: 
1 2 3 4 5 6 
BFS traversal of mirror: 
1 3 2 6 5 4 
What would you like to do? quit
 
Case 2:
Menu (this assumes no duplicate keys)
insert <data> at root
insert <data> left of <data>
insert <data> right of <data>
mirror
quit
What would you like to do? insert 1 at root
What would you like to do? mirror
Creating mirror copy...
BFS traversal of original tree: 
1 
BFS traversal of mirror: 
1 
What would you like to do? insert 2 left of 1
What would you like to do? insert 3 right of 1
What would you like to do? mirror
Creating mirror copy...
BFS traversal of original tree: 
1 2 3 
BFS traversal of mirror: 
1 3 2 
What would you like to do? quit

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.