-
Notifications
You must be signed in to change notification settings - Fork 11
/
Copy pathquestion5.c
199 lines (173 loc) · 5.14 KB
/
question5.c
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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
/*
Find lowest common ancestor of given two nodes in a binary search tree
Where the path to the parent for two nodes meet for the first time, that is the lowest common ancestor
//METHOD1
Since this is a binary search tree, we can search for two elements given say (10,20) and we can store the path of it
that is the elements in the way in an array for both the searches. Then we can compare both the arrays and see
where they are common at the max index. That index value is the least common incestor.
Time complexity: O(h) for search which in worst case can be O(n)
Space complexoty: O(h) for storing the path which in worst case can be O(n)
//METHOD2
We can do a simultaneous search for this. There is no need to store the path in an array in this case. If we see the
search splitting at a node, that is one element is smaller and one is greater than the node value, then that node
is the lowest common ancestor. If we see one value to be found as the node value itself, and the other node is
either greater or smaller than the node, then that node in this case also is the lowest common ancestor.
Time complexity: O(h) or O(n) //worst case
Space complexity: O(1) //if we do not do it using recursion else O(n)
Variation of this prob can be that, children have backlinks to the parent, then find the lowest common ancestor.
In this case we can apply a method similar to the linked list where two linkedlist were getting merged into a single
one and we had to find the merging point. Therefore, in this case, we can see the height of both the nodes given from
the root and we can traverse from child to parent level by level alternatively and see where they meet. Both the nodes,
need to be brought at the same level for this. Therefore finding height is important. But there wont be any difference
to the time or space complexity given.
*/
//METHOD1
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
struct node{
int data;
struct node *left;
struct node *right;
};
struct node *root = NULL;
struct node *newNode(int data){
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void search(struct node *t, int data){
if(data < t->data && t->left != NULL){
search(t->left, data);
}else if(data < t->data && t->left == NULL){
t->left = newNode(data);
}else if(data > t->data && t->right != NULL){
search(t->right,data);
}else{
t->right = newNode(data);
}
}
void insertNode(int data){
if(!root){
root = newNode(data);
return;
}
search(root, data);
}
void inorder(struct node *t){
if(t){
if(t->left){
inorder(t->left);
}
printf("%d ->", t->data);
if(t->right){
inorder(t->right);
}
}
}
void binarySearch(struct node *root,int *arr,int num){
if(!root){
return;
}
int size = sizeof(arr)/sizeof(arr[0]);
printf("size inside whjiel filling is... %d\n", size);
if(num > root->data){
binarySearch(root->right,arr,num);
}else if(num == root->data){
return;
}else{
binarySearch(root->left,arr,num);
}
}
void lowestAncestor(){
int num1, num2;
printf("Enter two numbers from the the BST\n");
scanf("%d",&num1);
scanf("%d",&num2);
int arr1[MAX], arr2[MAX];
binarySearch(root,arr1,num1);
binarySearch(root,arr2,num2);
int size1 = sizeof(arr1)/sizeof(arr1[0]);
int size2 = sizeof(arr2)/sizeof(arr2[0]);
int size = (size1 < size2)?size1:size2;
printf("size is..... %d\n", size);
int ancestor;
for(int i=0; i<size; i++){
printf("value from 1: %d\n", arr1[i]);
printf("value from 2: %d\n", arr2[i]);
if(arr1[i] == arr2[i]){
ancestor = arr1[i];
}
}
printf("ancestor is: %d\n", ancestor);
}
void multipleSearch(struct node *root, int num1, int num2){
if(!root){
return;
}
if(num1 < root->data && num2 < root->data){
return multipleSearch(root->left, num1,num2);
}
if(num1 > root->data && num2 > root->data){
return multipleSearch(root->right, num1, num2);
}
printf("ancestor is %d\n", root->data);
}
void lowestAncestorDiversion(){
int num1, num2;
printf("enter two numbers from the BST\n");
scanf("%d",&num1);
scanf("%d",&num2);
multipleSearch(root,num1, num2);
}
void iterativeSearch(struct node *root, int num1, int num2){
if(!root){
return;
}
while(root){
if(num1 < root->data && num2 < root->data){
root = root->left;
}else if(num2 > root->data && num1 > root->data){
root = root->right;
}else{
break;
}
}
printf("ancestor is %d\n", root->data);
}
void LCA(){
int num1, num2;
printf("enter two numbers from the BST\n");
scanf("%d",&num1);
scanf("%d",&num2);
iterativeSearch(root, num1, num2);
}
int main(){
int step, data;
while(1){
printf("1. Insert element\n");
printf("2. Print tree\n");
printf("3. lowest common ancestor using arrays\n");
printf("4. lowest common ancestor using diversion recursive\n");
printf("5. lowest common ancestor using diversion iterative\n");
scanf("%d",&step);
switch(step){
case 1: printf("enter element to be inserted\n");
scanf("%d",&data);
insertNode(data);
break;
case 2:inorder(root);
printf("\n");
break;
case 3: lowestAncestor();
break;
case 4: lowestAncestorDiversion();
break;
case 5: LCA();
break;
}
}
return 0;
}