Advertisement
lodha1503

Untitled

Feb 13th, 2022
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.65 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5.  
  6. struct node{
  7. int val;
  8. struct node* next;
  9. struct node* prev;
  10. };
  11.  
  12. void inorder(struct node* root) // Inorder and postorder traversal is made by to check whether the tree is crt or not.
  13. {
  14. if (root == NULL)
  15. return;
  16. inorder(root->prev);
  17. printf("%d ",&(root->val));
  18. inorder(root->next);
  19. }
  20.  
  21. void poorder(struct node* root)
  22. {
  23. if (root == NULL)
  24. return;
  25. poorder(root->prev);
  26. poorder(root->next);
  27. printf("%d ",&(root->val));
  28. }
  29.  
  30. void pop(struct node* stack){
  31. stack=stack->prev;
  32. if(stack!=NULL) stack->next=NULL;
  33. }
  34.  
  35. void push(struct node* stack, struct node* temp)
  36. {
  37. struct node* Node=(struct node *)malloc(sizeof(struct node));
  38.  
  39. if(stack==NULL){
  40. Node=temp;
  41. stack=Node;
  42. }else{
  43. Node=temp;
  44. stack->next=Node;
  45. Node->prev=stack;
  46. stack=Node;
  47. }
  48. };
  49.  
  50.  
  51.  
  52.  
  53. int main(){
  54. int n;
  55. scanf("%d",&n);
  56. int in[n],po[n];
  57. for(int i=0;i<n;i++){
  58. scanf("%d",&in[i]);
  59. }
  60. for(int i=0;i<n;i++){
  61. scanf("%d",&po[i]);
  62. }
  63.  
  64. // initialized indexes
  65. int po_index=n-1,in_index=n-1,flag=0;
  66. // created stack, root and previous
  67. struct node* root=(struct node *)malloc(sizeof(struct node));
  68. struct node* stack=NULL;
  69. struct node* previ;
  70. root->val=(po[po_index]);
  71. root->next=NULL;
  72. root->prev=NULL;
  73. --po_index;
  74. push(stack,root);
  75. // intitalized prev
  76. previ=root;
  77.  
  78. while(po_index>=0)
  79. {
  80. if(stack!=NULL && (in[in_index])==(stack->val)){
  81. previ=stack;
  82. pop(stack);
  83. --in_index;
  84. flag = 1;
  85. // no bug till now
  86. }else{
  87. // new node created
  88. struct node* temp=(struct node *)malloc(sizeof(struct node));
  89. // values assigned to the new node
  90. temp->val=(po[po_index]);
  91. temp->next=NULL;
  92. temp->prev=NULL;
  93. if(flag==0){
  94. previ->next = temp;
  95. previ = temp;
  96. }else{
  97. previ->prev= temp;
  98. previ = temp;
  99. flag=0;
  100. }
  101. push(stack,temp);
  102. --po_index;
  103. }
  104. }
  105. printf("%d",root->next->next->val); // No error when I am printing the right part but if I print "root->left>val" it is giving me some garbage value.
  106.  
  107. // The rest of the code written below is to check whether the tree is crt or not.
  108. // inorder(root);
  109. // printf("\n");
  110. // poorder(root);
  111. // printf("\n");
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement