forked from starrohan999/Hacktoberfest-Accepted
-
Notifications
You must be signed in to change notification settings - Fork 0
/
BST from InOrder and LevelOrder
60 lines (51 loc) · 1.23 KB
/
BST from InOrder and LevelOrder
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
//create a tree when levelorder and inorder is given
#include <bits/stdc++.h>
using namespace std;
//Class Structure of the Node
class Node {
node *left, *right;
int data;
}*root=nullptr;
//Function to Create a new Node
Node *NewNode(int data) {
Node *nn = new Node;
nn->left = nullptr;
nn->right = nullptr;
nn->data = data;
return nn;
}
void Inorder(Node *root) {
if(root == nullptr)
return;
InOrder(root->left);
cout<<root->data;
InOrder(root->right);
}
Node* CreateTree(int *inorder, int start, int last, unordered_map<int, int> map) {
if(start > last)
return nullptr;
int index = start;
for(int j=start+1; j<=last; j++) {
if(map[inorder[j]]<map[inorder[index]])
index = j;
}
Node* root = NewNode(inorder[index]);
root->left = CreateNode(inorder,start,index-1,map);
root->rigth = CreateNode(inorder,start,index-1,map);
}
Node* BuildTree(int *inorder, int *levelorder, int n) {
unordered_map<int, int> map;
for(int i=0; i<n; i++) {
map[levelorder[i]] = i;
}
return CreateTree(inorder, 0, n-1, map);
}
int main()
{
// Inorder Traversal
int inorder[] = {4,2,5,1,6,3,7};
// Level Order Traversal
int levelorder[] = {1,2,3,4,5,6,7};
int n = sizeof(inorder)/sizeof(inorder[0]);
BuildTree(inorder, levelorder, n);
}