ProDeveloperTutorial.com

Tutorials and Programming Solutions
Menu
  • Shell Scripting
  • System Design
  • Linux System Programming
  • 4g LTE
  • Coding questions
  • C
  • C++
  • DSA
  • GIT

Print all the paths from root node to leaf node

prodevelopertutorial March 30, 2020

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:

Print all the paths from root node to leaf node

 

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:

  1. Go to the left sub tree till null
  2. Print the root node
  3. 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:

Print all the paths from root node to leaf node

 

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:

 

Print all the paths from root node to leaf node

 

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

List Of Tutorials available in this website:

C Programming 20+ ChaptersC++ Programming 80+ Chapters
100+ Solved Coding QuestionsData Structures and Algorithms 85+ Chapters
System design 20+ ChaptersShell Scripting 12 Chapters
4g LTE 60+ ChaptersMost Frequently asked Coding questions
5G NR 50+ ChaptersLinux System Programming 20+ chapters
Share
Email
Tweet
Linkedin
Reddit
Stumble
Pinterest
Prev Article
Next Article

About The Author

prodevelopertutorial

Daily we discuss about competitive programming questions, join us at:   Telegram Channel

ProDeveloperTutorial.com

Tutorials and Programming Solutions
Copyright © 2021 ProDeveloperTutorial.com
Get top courses from: Educative.io