Print all root to leaf paths with there relative positions | Python3 program to print the longest leaf to leaf path ; Tree node structure used in the program ; Prints given root to leafAllpaths with underscores ; Find the minimum horizontal distance value in current root to leafAllpaths ; Find minimum horizontal distance ; Print the root to leafAllpaths with " _ " that indicate the related position ; Current tree node ; Print underscore ; Print current key ; A utility function prall path from root to leaf working of this function is similar to function of " Print _ vertical _ order " : Prpaths of binary tree in vertical order https : www . geeksforgeeks . org / print - binary - tree - vertical - order - set - 2 / ; Base case ; Leaf node ; Add leaf node and then prpath ; Store current path information ; Call left sub_tree ; Call left sub_tree ; Base case ; Driver code
MAX_PATH_SIZE = 1000 NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def printPath ( size ) : NEW_LINE INDENT minimum_Hd = 10 ** 19 NEW_LINE p = [ ] NEW_LINE global Allpaths NEW_LINE for it in range ( size ) : NEW_LINE INDENT p = Allpaths [ it ] NEW_LINE minimum_Hd = min ( minimum_Hd , p [ 0 ] ) NEW_LINE DEDENT for it in range ( size ) : NEW_LINE INDENT p = Allpaths [ it ] NEW_LINE noOfUnderScores = abs ( p [ 0 ] - minimum_Hd ) NEW_LINE for i in range ( noOfUnderScores ) : NEW_LINE INDENT print ( end = " _ ▁ " ) NEW_LINE DEDENT print ( p [ 1 ] ) NEW_LINE DEDENT print ( " = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = " ) NEW_LINE DEDENT def printAllPathsUtil ( root , HD , order ) : NEW_LINE INDENT global Allpaths NEW_LINE if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT Allpaths [ order ] = [ HD , root . data ] NEW_LINE printPath ( order + 1 ) NEW_LINE return NEW_LINE DEDENT Allpaths [ order ] = [ HD , root . data ] NEW_LINE printAllPathsUtil ( root . left , HD - 1 , order + 1 ) NEW_LINE printAllPathsUtil ( root . right , HD + 1 , order + 1 ) NEW_LINE DEDENT def printAllPaths ( root ) : NEW_LINE INDENT global Allpaths NEW_LINE if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT printAllPathsUtil ( root , 0 , 0 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT Allpaths = [ [ 0 , 0 ] for i in range ( MAX_PATH_SIZE ) ] NEW_LINE root = Node ( ' A ' ) NEW_LINE root . left = Node ( ' B ' ) NEW_LINE root . right = Node ( ' C ' ) NEW_LINE root . left . left = Node ( ' D ' ) NEW_LINE root . left . right = Node ( ' E ' ) NEW_LINE root . right . left = Node ( ' F ' ) NEW_LINE root . right . right = Node ( ' G ' ) NEW_LINE printAllPaths ( root ) NEW_LINE DEDENT