To print all the root to leaf paths we have used recursive approach.
The idea is to maintain a list of nodes on the paths and to print the list while leaf node is reached.
Algorithm:
Pre-requisite:
Input binary tree root, list a
FUNCTION printpathrecursively(Node* current_node, list a){
1. base case
IF(current_node ==NULL)
return;
END IF
2. append current_node ->data to the list;
IFcurrent_nodeis leaf node //leaf node reached
Print the list; //printing the root to leaf path
END IF
3. printpathrecursively(current_node->left,a);//recur for left subtree
printpathrecursively(current_node->right,a);//recur for right subtree
END FUNCTION
In the main function create an empty list a, And call printpathrecursively(root, a);
Example with explanation:
Nodes are represented by their respective values.
In main we call printpathrecursively(root, a)
----------------------------------------------
printpathrecursively(8, a)
current node not NULL
append 8 to list a
list: 8
current node is not leaf node
call to printpathrecursively(8->left, a)
call to printpathrecursively(8->right, a)
----------------------------------------------
printpathrecursively(8->left, a):
=printpathrecursively(5, a)
current node not NULL
append 5 to list a
list: 8,5
current node is not leaf node
call to printpathrecursively(5->left, a)
call to printpathrecursively(5->right, a)
----------------------------------------------
printpathrecursively(5->left, a):
=printpathrecursively(9, a)
current node not NULL
append 9 to list a
list: 8,5, 9
current node is leaf node
Print the list
call to printpathrecursively(9->left, a)
call to printpathrecursively(9->right, a)
call to printpathrecursively(9->left, a)
----------------------------------------------
=printpathrecursively(NULL, a)
current nodeNULL
control return to FUNCTION printpathrecursively(9, a)
At printpathrecursively(9, a)
call to printpathrecursively(9->right, a)
----------------------------------------------
=printpathrecursively(NULL, a)
current node NULL
control return to FUNCTION printpathrecursively(9, a)
At printpathrecursively(9, a)
Control reaches end of the void function
Thus control returns to the calleefunction printpathrecursively(5, a)
printpathrecursively(5->right, a):
----------------------------------------------
=printpathrecursively(7, a)
current node not NULL
append 7 to list a
list: 8, 5, 7 //Don’t think list will be 8, 5, 9, 7.
List at this function was 8, 5 not 8, 5, 9
//List has not been passed by referenced
current node is not leaf node
call to printpathrecursively(7->left, a)
call to printpathrecursively(7->right, a)
This can be carried out until control gets back to main
which called function printpathrecursively(root, a)
You can do rest by your own to have much more clear idea about how the program is actually working.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
//tree node
class Node{
public:
int data;
Node *left;
Node *right;
};
void print(vector<int> a){
for(int i=0;i<a.size();i++){
if(i==a.size()-1)
cout<<a[i];
else
cout<<a[i]<<"->";
}
}
void printpathrecursively(Node* root,vector<int> a){
if(root==NULL) //base case
return ;
a.push_back(root->data);
if(!root->left && !root->right){ //leaf node reached
print(a);
cout<<endl;
}
printpathrecursively(root->left,a);//recur for left subtree
printpathrecursively(root->right,a);//recur for right subtree
}
void printPaths(Node* root)
{
vector<int> a;
printpathrecursively(root,a);
}
//creating new nodes
Node* newnode(int data){
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main() {
//**same tree is builted as shown in example**
cout<<"tree in the example is build here"<<endl;
//building the tree like as in the example
Node *root=newnode(8);
root->left= newnode(5);
root->right= newnode(4);
root->right->right=newnode(11);
root->right->right->left=newnode(3);
root->left->left=newnode(9);
root->left->right=newnode(7);
root->left->right->left=newnode(1);
root->left->right->right=newnode(12);
root->left->right->right->left=newnode(2);
cout<<"Printing all root to leaf paths......"<<endl;
printPaths(root);
return 0;
}
Output
tree in the example is build here
Printing all root to leaf paths......
8->5->9
8->5->7->1
8->5->7->12->2
8->4->11->3
To print all the root to leaf paths we have used recursive approach.
The idea is to maintain a list of nodes on the paths and to print the list while leaf node is reached.
Algorithm:
Pre-requisite:
Input binary tree root, list a
In the main function create an empty list a, And call printpathrecursively(root, a);
Example with explanation:
Nodes are represented by their respective values.
You can do rest by your own to have much more clear idea about how the program is actually working.
C++ Implementation:
Output