SHARE
TWEET

print all paths to node without recursion

prakharvk Jun 18th, 2019 49 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /* A binary tree node has key, pointer to left
  5. child and a pointer to right child */
  6. struct Node
  7. {
  8.     int key;
  9.     struct Node* left, *right;
  10. };
  11.  
  12. /* To create a newNode of tree and return pointer */
  13. struct Node* newNode(int key)
  14. {
  15.     Node* temp = new Node;
  16.     temp->key = key;
  17.     temp->left = temp->right = NULL;
  18.     return (temp);
  19. }
  20.  
  21. void print(vector<int>&v){
  22.     int n=v.size();
  23.     if(n==0)
  24.         return;
  25.     for(int i=0;i<v.size();i++){
  26.         cout<<v[i]<<" ";
  27.     }
  28.     cout<<endl;
  29. }
  30.  
  31.  
  32. void printPaths(Node *root,vector<int>&v){
  33.     if(root==NULL)
  34.         return;
  35.    
  36.     v.push_back(root->key);    
  37.     if(root->left==NULL&&root->right==NULL){
  38.         print(v);
  39.         v.pop_back();
  40.        return;
  41.     }    
  42.    
  43.     printPaths(root->left,v);
  44.     printPaths(root->right,v);
  45.     v.pop_back();
  46. }
  47.  
  48.  
  49. void printUP(Node *root,map<Node*,Node*>mp){
  50.     if(root==NULL)
  51.         return;
  52.     printUP(mp[root],mp);
  53.     cout<<root->key<<" ";
  54. }
  55.    
  56.  
  57. void printPathsIt(Node *root){
  58.     if(root==NULL)
  59.         return;
  60.     stack<Node*>st;
  61.     st.push(root);
  62.     map<Node*,Node*>mp;
  63.     mp[root]=NULL;
  64.     while(!st.empty()){
  65.         Node *temp=st.top();
  66.         st.pop();
  67.         if(!temp->left&&!temp->right){
  68.             printUP(temp,mp);
  69.             cout<<endl;
  70.             continue;
  71.         }
  72.  
  73.         if(temp->right){
  74.             st.push(temp->right);
  75.             mp[temp->right]=temp;
  76.         }
  77.         if(temp->left){
  78.             st.push(temp->left);
  79.             mp[temp->left]=temp;
  80.         }  
  81.     }
  82. }
  83.  
  84.  
  85. void inorder(Node* root)
  86. {
  87.     if (root)
  88.     {
  89.         inorder(root->left);
  90.         printf("%d ", root->key);
  91.         inorder(root->right);
  92.     }
  93. }
  94.  
  95. // Driver program to test above functions
  96. int main()
  97. {
  98.     // Making above given diagram's binary tree
  99.     Node* root = newNode(8);
  100.     root->left = newNode(3);
  101.  
  102.     root->left->left = newNode(1);
  103.     root->left->right = newNode(6);
  104.     root->left->right->left = newNode(4);
  105.     root->left->right->right = newNode(7);
  106.  
  107.     root->right = newNode(10);
  108.     root->right->right = newNode(14);
  109.     root->right->right->left = newNode(13);
  110.  
  111.     //inorder(root);
  112.     vector<int>v;
  113.     // printPaths(root,v);
  114.     printPathsIt(root);
  115. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top