Q:

Given a Binary Tree of size N, write a program that prints all the possible paths from root node to the all the leaf node\'s of the binary tree

mahmoud2506
Save to bookmark
|
2022-04-30
|
  247 
0

All Root to Leaf Paths

Given a Binary Tree of size N, write a program that prints all the possible paths from root node to the all the leaf node's of the binary tree.

Example:

Let us the tree be like following:

All Root to Leaf Paths

All possible root to leaf paths in this tree is:

    8->5->9
    8->5->7->1
    8->5->7->12->2
    8->4->11->3
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

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:

All Root to Leaf Paths

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | tree
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a binary tree, where every node value is a n... >>
<< Given a Binary Tree and a target key, write a func...