Print all root to leaf paths with there relative positions | C ++ 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 program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_PATH_SIZE  1000 NEW_LINE struct Node { char data ; Node * left , * right ; } ; Node * newNode ( char data ) { struct Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } struct PATH { int Hd ; char key ; } ; void printPath ( vector < PATH > path , int size ) { int minimum_Hd = INT_MAX ; PATH p ; for ( int it = 0 ; it < size ; it ++ ) { p = path [ it ] ; minimum_Hd = min ( minimum_Hd , p . Hd ) ; } for ( int it = 0 ; it < size ; it ++ ) { p = path [ it ] ; int noOfUnderScores = abs ( p . Hd - minimum_Hd ) ; for ( int i = 0 ; i < noOfUnderScores ; i ++ ) cout << " _ ▁ " ; cout << p . key << endl ; } cout << " = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = " << endl ; } void printAllPathsUtil ( Node * root , vector < PATH > & AllPath , int HD , int order ) { if ( root == NULL ) return ; if ( root -> left == NULL && root -> right == NULL ) { AllPath [ order ] = ( PATH { HD , root -> data } ) ; printPath ( AllPath , order + 1 ) ; return ; } AllPath [ order ] = ( PATH { HD , root -> data } ) ; printAllPathsUtil ( root -> left , AllPath , HD - 1 , order + 1 ) ; printAllPathsUtil ( root -> right , AllPath , HD + 1 , order + 1 ) ; } void printAllPaths ( Node * root ) { if ( root == NULL ) return ; vector < PATH > Allpaths ( MAX_PATH_SIZE ) ; printAllPathsUtil ( root , Allpaths , 0 , 0 ) ; } int main ( ) { 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 ) ; return 0 ; }