Find mirror of a given node in Binary tree | Python3 program to find the mirror node in Binary tree ; A binary tree node has data , reference to left child and a reference to right child ; recursive function to find mirror ; If any of the node is none then node itself and decendent have no mirror , so return none , no need to further explore ! ; if left node is target node , then return right 's key (that is mirror) and vice versa ; first recur external nodes ; if no mirror found , recur internal nodes ; interface for mirror search ; Driver ; target node whose mirror have to be searched
class Node : NEW_LINE INDENT def __init__ ( self , key , lchild = None , rchild = None ) : NEW_LINE INDENT self . key = key NEW_LINE self . lchild = None NEW_LINE self . rchild = None NEW_LINE DEDENT DEDENT def findMirrorRec ( target , left , right ) : NEW_LINE INDENT if left == None or right == None : NEW_LINE INDENT return None NEW_LINE DEDENT if left . key == target : NEW_LINE INDENT return right . key NEW_LINE DEDENT if right . key == target : NEW_LINE INDENT return left . key NEW_LINE DEDENT mirror_val = findMirrorRec ( target , left . lchild , right . rchild ) NEW_LINE if mirror_val != None : NEW_LINE INDENT return mirror_val NEW_LINE DEDENT findMirrorRec ( target , left . rchild , right . lchild ) NEW_LINE DEDENT def findMirror ( root , target ) : NEW_LINE INDENT if root == None : NEW_LINE INDENT return None NEW_LINE DEDENT if root . key == target : NEW_LINE INDENT return target NEW_LINE DEDENT return findMirrorRec ( target , root . lchild , root . rchild ) NEW_LINE DEDENT def main ( ) : NEW_LINE INDENT root = Node ( 1 ) NEW_LINE n1 = Node ( 2 ) NEW_LINE n2 = Node ( 3 ) NEW_LINE root . lchild = n1 NEW_LINE root . rchild = n2 NEW_LINE n3 = Node ( 4 ) NEW_LINE n4 = Node ( 5 ) NEW_LINE n5 = Node ( 6 ) NEW_LINE n1 . lchild = n3 NEW_LINE n2 . lchild = n4 NEW_LINE n2 . rchild = n5 NEW_LINE n6 = Node ( 7 ) NEW_LINE n7 = Node ( 8 ) NEW_LINE n8 = Node ( 9 ) NEW_LINE n3 . rchild = n6 NEW_LINE n4 . lchild = n7 NEW_LINE n4 . rchild = n8 NEW_LINE target = n3 . key NEW_LINE mirror = findMirror ( root , target ) NEW_LINE print ( " Mirror ▁ of ▁ node ▁ { } ▁ is ▁ node ▁ { } " . format ( target , mirror ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT main ( ) NEW_LINE DEDENT