Print all root to leaf paths with there relative positions
Given a binary tree, print the root to the leaf path, but add “_” to indicate the relative position.
Input : Root of below tree A / \ B C / \ / \ D E F G Output : All root to leaf paths _ _ A _ B D _ A B _ E A _ C F A _ C _ _ G
Below is complete algorithm :
1) We do Preorder traversal of the given Binary Tree. While traversing the tree, we can recursively calculate horizontal distances or HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1. For every HD value, we maintain a list of nodes in a vector (” that will store information of current node horizontal distance and key value of root “).we also maintain the order of node (order in which they appear in path from root to leaf). for maintaining the order,here we used vector.
2) While we reach to leaf node during traverse we print that path with underscore “_”
Print_Path_with_underscore function
……a) First find the minimum Horizontal distance of the current path.
……b) After that we traverse current path
……….First Print number of underscore “_” : abs (current_node_HD – minimum-HD)
……….Print current node value.
2) While we reach to leaf node during traverse we print that path with underscore “_”
Print_Path_with_underscore function
……a) First find the minimum Horizontal distance of the current path.
……b) After that we traverse current path
……….First Print number of underscore “_” : abs (current_node_HD – minimum-HD)
……….Print current node value.
// 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
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);
}