// C++ program to print all root to leaf paths

// with there relative position

#include<bits/stdc++.h>

using namespace std;

#define MAX_PATH_SIZE 1000

// tree structure

struct Node

{

char data;

Node *left, *right;

};

// function create new node

Node * newNode(char data)

{

struct Node *temp = new Node;

temp->data = data;

temp->left = temp->right = NULL;

return temp;

}

// store path information

struct PATH

{

int Hd; // horigontal distance of node from root.

char key; // store key

};

// Prints given root to leaf path with underscores

void printPath(vector < PATH > path, int size)

{

// Find the minimum horizontal distance value

// in current root to leaf path

int minimum_Hd = INT_MAX;

PATH p;

// find minimum horizontal distance

for (int it=0; it<size; it++)

{

p = path[it];

minimum_Hd = min(minimum_Hd, p.Hd);

}

// print the root to leaf path with "_"

// that indicate the related position

for (int it=0; it < size; it++)

{

// current tree node

p = path[it];

int noOfUnderScores = abs(p.Hd - minimum_Hd);

// print underscore

for (int i = 0; i < noOfUnderScores; i++)

cout << "_ ";

// print current key

cout << p.key << endl;

}

cout << "==============================" << endl;

}

// 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

// https://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

void printAllPathsUtil(Node *root,

vector < PATH > &AllPath,

int HD, int order )

{

// base case

if(root == NULL)

return;

// leaf node

if (root->left == NULL && root->right == NULL)

{

// add leaf node and then print path

AllPath[order] = (PATH { HD, root->data });

printPath(AllPath, order+1);

return;

}

// store current path information

AllPath[order] = (PATH { HD, root->data });

// call left sub_tree

printAllPathsUtil(root->left, AllPath, HD-1, order+1);

//call left sub_tree

printAllPathsUtil(root->right, AllPath, HD+1, order+1);

}

void printAllPaths(Node *root)

{

// base case

if (root == NULL)

return;

vector<PATH> Allpaths(MAX_PATH_SIZE);

printAllPathsUtil(root, Allpaths, 0, 0);

}

// Driver program to test above function

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;

}