Advertisement
Kali_prasad

zigzag traversal

May 7th, 2022
26
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 KB | None | 0 0
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. /*3 2 4 1 5
  8.        3
  9.       / \
  10.      2   4
  11.     /     \
  12.    1       5
  13.  
  14.  
  15.  
  16. */
  17. typedef long long ll;
  18. typedef pair<int, int> pii;
  19. typedef pair<string,int> psi;
  20. typedef unordered_map<int,int> mii;
  21. typedef unordered_map<long long,long long> mll;
  22. typedef unordered_map<string,int> msi;
  23. typedef unordered_map<char,int> mci;
  24. typedef unordered_set<int> si;
  25. typedef unordered_set<long long> sll;
  26. typedef unordered_set<string> ss;
  27. typedef unordered_set<char> sc;
  28. typedef map<int,int> ormii;
  29. typedef map<long long,long long> ormll;
  30. typedef map<string,int> ormsi;
  31. typedef map<char,int> ormci;
  32. typedef set<int> orsi;
  33. typedef set<long long> orsll;
  34. typedef set<string> orss;
  35. typedef set<char> orsc;
  36. typedef vector<int> vi;
  37. typedef vector<string> vs;
  38. typedef vector<char> vc;
  39. typedef vector<ll> vll;
  40. typedef vector<vector<int>> vvi;
  41. typedef vector<vector<string>> vvs;
  42. typedef vector<vector<ll>> vvll;
  43.  
  44. #define FOR(i, a, b) for (auto i=a; i<=(b); i++)
  45. #define FORd(i,b,a) for (int i =b; i >= a; i--)
  46. #define sortinc(v)  sort(v.begin(),v.end())
  47. #define sortdec(v)  sort(v.rbegin(),v.rend())
  48. #define sz(x) (int)(x).size()
  49. #define mp make_pair
  50. #define pb push_back
  51. #define pob pop_back
  52. #define pf push_front
  53. #define pof pop_front
  54. #define fi first
  55. #define se second
  56. #define ins insert
  57.  
  58. const int MOD = 1000000007;
  59. //type functions here
  60. class Node
  61. {
  62.     public:
  63.   Node* left;
  64.     Node* right;
  65.     int data;
  66.     Node(int d)
  67.     {
  68.         data=d;
  69.         left=NULL;
  70.         right=NULL;
  71.     }
  72. };
  73. void LevelOrder(Node* head)
  74. {
  75.     queue<Node*> q;
  76.     q.push(head);
  77.     int z=1;
  78.     while(!q.empty())
  79.     {
  80.         int sizee=sz(q);
  81.         FOR(i,1,sizee)
  82.         {
  83.             Node* temp=q.front();
  84.             q.pop();
  85.             cout<<temp->data<<" ";
  86.             //cout<<z<<" ";
  87.             if(z%2!=0){
  88.             if(temp->left) q.push(temp->left);
  89.             if(temp->right) q.push(temp->right);
  90.             }
  91.             else
  92.             {
  93.              if(temp->right) q.push(temp->right);
  94.              if(temp->left) q.push(temp->left);
  95.            
  96.             }
  97.         }
  98.         z++;
  99.         //cout<<endl;
  100.        
  101.     }
  102.    
  103. }
  104. Node* insert(Node* head,int d)
  105. {
  106.     if(head==NULL) return new Node(d);
  107.     if(d<head->data)
  108.     {
  109.         head->left=insert(head->left,d);
  110.     }
  111.     else
  112.     {
  113.         head->right=insert(head->right,d);
  114.     }
  115.     return head;
  116. }
  117. int main() {
  118.     ios_base::sync_with_stdio(false);
  119.     cin.tie(NULL);
  120.    
  121.     int tc=1;
  122.     cin>>tc;
  123.     FOR(w,1,tc)
  124.     {
  125.       Node* head=NULL;
  126.         int n;
  127.         cin>>n;
  128.         while(n)
  129.         {
  130.             int temp;
  131.             cin>>temp;
  132.             head=insert(head,temp) ;          
  133.             n--;
  134.         }
  135.         LevelOrder(head);
  136.         cout<<endl;
  137.        
  138.     }
  139.     return 0;
  140. }
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement