In this chapter we shall see how to print all the paths from root to leaf nodes.
Problem Statement:
You are given the root node of a binary tree, you need to print all the paths from root node to leaf nodes.
Consider the example below:
Now according to the image, we have root node “a” and leaf nodes “h”, “e”, “f”, “g”.
So according to the question you need to print all the paths:
a -> b -> d -> h
a -> b -> e
a -> c -> f
a -> c -> g
Now we shall see how to solve this problem:
To solve this problem, we shall use inorder traversal and stack.
Below is how to preform inorder traversal:
- Go to the left sub tree till null
- Print the root node
- Go to the right sub tree
So where does stack comes into picture?
Let’s understand with help of an example:
In the above image, if we apply inorder traversal on the root node, we traverse as below:
a -> b -> d -> h
Now according to inorder traversal, you will print h. But according to the question you need to print the complete path.
At that time stack will be useful.
As shown below in the image, the stack will look like below:
Now once we reach the leaf node, we shall print the whole content of the stack.
But when shall we pop from the stack?
We shall pop the top element when we print that node, and go to the parent of that node.
i.e once we have printed the node “h”, go to it’s parent node “d”. For “d” there is no right child. Hence we return to “b”. At the same time, we remove both “h” and “d” node.
For node “b” there is a right child, we insert “e” into the stack as shown below:
Now as “e” is the leaf node, we print the content of the stack
i.e a -> b -> e
Similarly, we have visited all the children of node “b”, hence we remove “e” and “b” from the stack.
And now we reach the root node “a”. Node “A” has right child “c” from “c” we go to “f” and follow the same procedure.
Link this we print all the paths from root to leaf nodes.
Solution in C++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
void print_root_to_leaf_paths(Node* node, vector<int> &my_path)
{
if (node == NULL)
return;
my_path.push_back(node->data);
if (node->left == NULL && node->right == NULL)
{
for (int data: my_path)
cout << data << " ";
cout << endl;
}
print_root_to_leaf_paths(node->left, my_path);
print_root_to_leaf_paths(node->right, my_path);
my_path.pop_back();
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
vector<int> my_path;
print_root_to_leaf_paths(root, my_path);
return 0;
}
Output:
16 10 7 16 10 15 16 25 18 16 25 30
