DESCRIPTION:

In this c++ article i am going to explain how to print the nodes from root to leaf in binary tree .According to binary tree concept we need to traverse through the whole tree to print each path from root to leaf .In this program preorder traversal is used. There can be multiple paths  and as it is wrote without recursion so it will be using stack and map concept

for example : different paths for the following binary tree : PATHS ARE BEEN MARKED BY RED 

ALGORITHM:

1.      First the input will be binary tree.

        after that  current variable will traverse through the binary tree in which there will three conditions 

3.      case 1: if the current node has right node value then it will be stored in stack nodeStack1

4.      case 2:  if the current node has left node value then it will be stored in stack  nodeStack1

5.      case 3: if the current node doesn't have either right or left or both the nodes then the control will be shifted to printValues  function where it push the elements from bottom to  top and the print the values by poping out the top values .

 INPUT:

 Input is pre-defined if user want to change the values the user have to make changes in the program itself.

 CODE:

#include <bits/stdc++.h> 

using namespace std;

struct Node 

{ 

int data; 

struct Node *left, *right; 

}; 

Node* new1(int data) 

{ 

Node* node = new Node; 

node->data = data; 

node->left = node->right = NULL; 

return node; 

} 

void printValues(Node* current, map<Node*, Node*> parent) ;

void traverse(Node* root) ;

int main() 

{ 

Node* r1 = new1(68); 

r1->left = new1(69); 

r1->right = new1(92); 

r1->left->left = new1(98); 

r1->left->right = new1(20); 

r1->right->left = new1(63); 

traverse(r1); 

return 0; 

} 

void printValues(Node* current, map<Node*, Node*> parent) 

{ 

stack<Node*> s1; 

while (current) 

{ 

s1.push(current); 

current = parent[current]; 

} 

while (s1.empty()==0) 

{ 

current = s1.top(); 

s1.pop(); 

cout << current->data << " "; 

} 

cout << endl; 

} 

void traverse(Node* root) 

{ 

if (root == NULL) 

return; 

    stack<Node*> nodeStack1; 

nodeStack1.push(root); 

map<Node*, Node*> parent; 

parent[root] = NULL; 

while (nodeStack1.empty()==0) 

{ 

Node* current = nodeStack1.top(); 

nodeStack1.pop(); 

if (current->right) 

{ 

parent[current->right] = current; 

nodeStack1.push(current->right); 

} 

if (current->left) 

{ 

parent[current->left] = current; 

nodeStack1.push(current->left); 

} 

if (!(current->left) && !(current->right)) 

printValues(current, parent); 

} 

}                     

EXPLANATION:

In this example the input be binary tree which is given below:

• this binary tree will transferred to the traverse function "traverse(Node* root)"
• in this function the values of the binary tree are saved in the map "parent" according to the three cases .to store the values in  the map "nodestack1" node is used.the values will be stored as shown below:
•  

• if     the third condition is valid it will be going to print the values using the stack s1 using pusing and poping values from the stack.