Problem:
Provided Inorder and PostOrder of a tree. Construct the tree and print it in PreOrder traversal.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
#include <stdio.h> #include <iostream> #include <string.h> #include<stdlib.h> #include <string> using namespace std; struct Node{ int data; Node *left; Node *right; }; int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } } void pintPreOrder(Node* res) { Node *tmp; if(res!=NULL) { cout<<res->data<<" "; if(res->left) pintPreOrder(res->left); if(res->right) pintPreOrder(res->right); } } Node* NewbuildTree(int in[],int post[],int in_stIndex,int in_endIndex,int *postOrderIdx) { if(in_stIndex>in_endIndex) return NULL; Node *tNode = new Node(); tNode->data=post[(*postOrderIdx)--]; tNode->left=NULL; tNode->right=NULL; if(in_stIndex==in_endIndex) return tNode; int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data); tNode->right=NewbuildTree(in,post,rootIndex+1,in_endIndex,postOrderIdx); tNode->left=NewbuildTree(in,post,in_stIndex,rootIndex-1,postOrderIdx); return tNode; } Node *buildTree(int in[], int post[], int n) { int postOrderIdx=n-1; NewbuildTree(in,post,0,n-1,&postOrderIdx); } int main() { int in[105]; int post[105]; int t,n; scanf("%d",&t); Node *res,*tmp; while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&in[i]); for(int i=0;i<n;i++) scanf("%d",&post[i]); res=buildTree(in,post,n); //cout<<"done"<<endl; pintPreOrder(res); } return 0; } |
The problem was provided as a functional problem in Amazon & Adobe interview as here [Courtesy : geeksforgeeks]
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
struct Node { int data; Node *left, *right; } int search(int in[],int in_stIndex,int in_endIndex,int data) { for(int i=in_stIndex;i<=in_endIndex;i++) { if(in[i]==data) return i; } } Node* NewbuildTree(int in[],int post[],int in_stIndex,int in_endIndex,int *postOrderIdx) { if(in_stIndex>in_endIndex) return NULL; Node *tNode = new Node(); tNode->data=post[(*postOrderIdx)--]; tNode->left=NULL; tNode->right=NULL; if(in_stIndex==in_endIndex) return tNode; int rootIndex = search(in,in_stIndex,in_endIndex,tNode->data); tNode->right=NewbuildTree(in,post,rootIndex+1,in_endIndex,postOrderIdx); tNode->left=NewbuildTree(in,post,in_stIndex,rootIndex-1,postOrderIdx); return tNode; } // Function should construct tree and return // root of it. in[] stores inorder traversal // post[] stores postorder traversal. n is // size of these arrays Node *buildTree(int in[], int post[], int n) { // Your code here int postOrderIdx=n-1; NewbuildTree(in,post,0,n-1,&postOrderIdx); } |