fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <stack>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9.  
  10.  
  11. struct TreeNode {
  12.   TreeNode *left, *right;
  13.   int data;
  14.   TreeNode(int val) : left(NULL), right(NULL), data(val) { }
  15. };
  16.  
  17.  
  18.  
  19. TreeNode* createTree(){
  20.   TreeNode* root=new TreeNode(45);
  21.   //level 2
  22.   root->left=new TreeNode(22);
  23.   root->right=new TreeNode(70);
  24.   //level 3
  25.   root->left->left=new TreeNode(15);
  26.   root->left->right=new TreeNode(27);
  27.   root->right->left=new TreeNode(60);
  28.   root->right->right=new TreeNode(80);
  29.  
  30.   return root;
  31. }
  32.  
  33.  
  34.  
  35. void printPath(const vector<int>& v){
  36.     cout<<"path "; 
  37.     for (auto& item : v){
  38.       cout<<item<<" ";
  39.     }
  40.     cout<<endl;
  41. }
  42.  
  43. bool isLeaf(const TreeNode* root){
  44.     return NULL==root->left && NULL ==root->right;
  45. }
  46.  
  47. void printAllPathRecursive(const TreeNode* root, vector<int> v){
  48.     if(isLeaf(root)) {
  49.         v.push_back(root->data);
  50.         printPath(v);
  51.         return;
  52.     }
  53.  
  54.  
  55.     v.push_back(root->data);
  56.  
  57.     printAllPathRecursive(root->left,v);
  58.     printAllPathRecursive(root->right,v);
  59.  
  60. }
  61.  
  62.  
  63.  
  64. void printAllPathNonRecursive(TreeNode* root){
  65.     if(NULL==root)
  66.         return;
  67.  
  68.     stack<TreeNode*> s;
  69.     stack<string> path;
  70.  
  71.     s.push(root);
  72.  
  73.     path.push(to_string(root->data)+" ");
  74.  
  75.     while(!s.empty()){
  76.         TreeNode* current=s.top();
  77.         s.pop();
  78.  
  79.         string currentPath=path.top();
  80.         path.pop();
  81.  
  82.         if(isLeaf(current)){
  83.             cout<<"path  "<< currentPath<<endl;
  84.             continue;
  85.         }
  86.  
  87.         if(current->left){
  88.            string leftString=currentPath+" "+to_string(current->left->data);
  89.            s.push(current->left);
  90.            path.push(leftString);
  91.         } 
  92.  
  93.         if(current->right){
  94.            string rightString=currentPath+" "+to_string(current->right->data);
  95.            s.push(current->right);
  96.            path.push(rightString);
  97.         }
  98.  
  99.     }
  100.  
  101. }
  102.  
  103.  
  104.  
  105. int main() {
  106.   TreeNode* fullBinaryTree=createTree();
  107.   vector<int> v;
  108.   //printAllPathRecursive(fullBinaryTree,v);
  109.   printAllPathNonRecursive(fullBinaryTree);
  110.  
  111.   return 0;
  112. }
Success #stdin #stdout 0s 3440KB
comments (?)
stdin 
Standard input is empty
stdout 
path  45  70 80
path  45  70 60
path  45  22 27
path  45  22 15
https://ideone.com/NyqYyS
print tree path
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!