Reverse tree path | A Binary Tree Node ; ' data ' is input . We need to reverse path from root to data . level ' ▁ is ▁ current ▁ level . ▁ ▁ temp ' that stores path nodes . nextpos ' used to pick next item for reversing. ; return None if root None ; Final condition if the node is found then ; store the value in it 's level ; change the root value with the current next element of the map ; increment in k for the next element ; store the data in perticular level ; We go to right only when left does not contain given data . This way we make sure that correct path node is stored in temp [ ] ; If current node is part of the path , then do reversing . ; return None if not element found ; Reverse Tree path ; store per level data ; it is for replacing the data ; reverse tree path ; INORDER ; Utility function to create a new tree node ; Driver code ; Let us create binary tree shown in above diagram ; 7 / \ 6 5 / \ / \ 4 3 2 1 ; Reverse Tree Path ; Traverse inorder
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def reverseTreePathUtil ( root , data , temp , level , nextpos ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return None , temp , nextpos ; NEW_LINE DEDENT if ( data == root . data ) : NEW_LINE INDENT temp [ level ] = root . data ; NEW_LINE root . data = temp [ nextpos ] ; NEW_LINE nextpos += 1 NEW_LINE return root , temp , nextpos ; NEW_LINE DEDENT temp [ level ] = root . data ; NEW_LINE right = None NEW_LINE left , temp , nextpos = reverseTreePathUtil ( root . left , data , temp , level + 1 , nextpos ) ; NEW_LINE if ( left == None ) : NEW_LINE INDENT right , temp , nextpos = reverseTreePathUtil ( root . right , data , temp , level + 1 , nextpos ) ; NEW_LINE DEDENT if ( left or right ) : NEW_LINE INDENT root . data = temp [ nextpos ] ; NEW_LINE nextpos += 1 NEW_LINE return ( left if left != None else right ) , temp , nextpos ; NEW_LINE DEDENT return None , temp , nextpos ; NEW_LINE DEDENT def reverseTreePath ( root , data ) : NEW_LINE INDENT temp = dict ( ) NEW_LINE nextpos = 0 ; NEW_LINE reverseTreePathUtil ( root , data , temp , 0 , nextpos ) ; NEW_LINE DEDENT def inorder ( root ) : NEW_LINE INDENT if ( root != None ) : NEW_LINE INDENT inorder ( root . left ) ; NEW_LINE print ( root . data , end = ' ▁ ' ) NEW_LINE inorder ( root . right ) ; NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT temp = Node ( data ) NEW_LINE return temp ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 7 ) ; NEW_LINE root . left = newNode ( 6 ) ; NEW_LINE root . right = newNode ( 5 ) ; NEW_LINE root . left . left = newNode ( 4 ) ; NEW_LINE root . left . right = newNode ( 3 ) ; NEW_LINE root . right . left = newNode ( 2 ) ; NEW_LINE root . right . right = newNode ( 1 ) ; NEW_LINE data = 4 ; NEW_LINE reverseTreePath ( root , data ) ; NEW_LINE inorder ( root ) ; NEW_LINE DEDENT