Print all root to leaf paths with there relative positions | Java program to print all root to leaf paths with there relative position ; tree structure ; Function create new node ; Store path information ; Prints given root to leaf path with underscores ; Find the minimum horizontal distance value in current root to leaf path ; Find minimum horizontal distance ; Print the root to leaf path with " _ " that indicate the related position ; Current tree node ; Print underscore ; Print current key ; A utility function print all path from root to leaf working of this function is similar to function of " Print _ vertical _ order " : Print paths of binary tree in vertical order www . geeksforgeeks . org / print - binary - tree - vertical - order - set - 2 / https : ; Base case ; Leaf node ; Add leaf node and then print path ; Store current path information ; Call left sub_tree ; Call left sub_tree ; Base case ; Driver code
import java . util . ArrayList ; class Graph { static final int MAX_PATH_SIZE = 1000 ; static class Node { char data ; Node left , right ; } ; static Node newNode ( char data ) { Node temp = new Node ( ) ; temp . data = data ; temp . left = temp . right = null ; return temp ; } static class PATH { int Hd ; char key ; public PATH ( int Hd , char key ) { this . Hd = Hd ; this . key = key ; } public PATH ( ) { } } ; static void printPath ( ArrayList < PATH > path , int size ) { int minimum_Hd = Integer . MAX_VALUE ; PATH p ; for ( int it = 0 ; it < size ; it ++ ) { p = path . get ( it ) ; minimum_Hd = Math . min ( minimum_Hd , p . Hd ) ; } for ( int it = 0 ; it < size ; it ++ ) { p = path . get ( it ) ; int noOfUnderScores = Math . abs ( p . Hd - minimum_Hd ) ; for ( int i = 0 ; i < noOfUnderScores ; i ++ ) System . out . print ( " _ " ) ; System . out . println ( p . key ) ; } System . out . println ( " = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = " ) ; } static void printAllPathsUtil ( Node root , ArrayList < PATH > AllPath , int HD , int order ) { if ( root == null ) return ; if ( root . left == null && root . right == null ) { AllPath . set ( order , new PATH ( HD , root . data ) ) ; printPath ( AllPath , order + 1 ) ; return ; } AllPath . set ( order , new PATH ( HD , root . data ) ) ; printAllPathsUtil ( root . left , AllPath , HD - 1 , order + 1 ) ; printAllPathsUtil ( root . right , AllPath , HD + 1 , order + 1 ) ; } static void printAllPaths ( Node root ) { if ( root == null ) return ; ArrayList < PATH > Allpaths = new ArrayList < > ( ) ; for ( int i = 0 ; i < MAX_PATH_SIZE ; i ++ ) { Allpaths . add ( new PATH ( ) ) ; } printAllPathsUtil ( root , Allpaths , 0 , 0 ) ; } public static void main ( String [ ] args ) { Node root = newNode ( ' A ' ) ; root . left = newNode ( ' B ' ) ; root . right = newNode ( ' C ' ) ; root . left . left = newNode ( ' D ' ) ; root . left . right = newNode ( ' E ' ) ; root . right . left = newNode ( ' F ' ) ; root . right . right = newNode ( ' G ' ) ; printAllPaths ( root ) ; } }