# Spoj ACPC10A solution. Spoj Whats Next solution.

This question is based on direct application of Arithmetic Progression‘s common difference and Geometric Progression‘ common ratio.

First check whether there is a common difference (c-b) and (b-a) , or whether there is common ratio (c/b) and (b/a).

### Spoj ACPC10A solution code:

```#include <bits/stdc++.h>
using namespace std;

int main() {
std::ios::sync_with_stdio(false);

int a,b,c;
cin>>a>>b>>c;

//will stop if all 3 are zeros
while(a!=0 || b!=0 || c!=0)
{
//if the series is AP
if((c-b) == (b-a))
{
// c-b = common difference
cout<<"AP "<<c+(c-b)<<"\n";
}
//else it is GP
else
{
// c/b = common ratio
cout<<"GP "<<c*(c/b)<<"\n";
}
cin>>a>>b>>c;
}
return 0;
}```

# Spoj PRISMSA solution. Spoj TRIANGULAR PRISM solution.

This question is of minimization of Surface Area for a Triangular Prism whose volume is given.
Applying the standard differentiating procedure, the value of “a” comes out to be:

a = (4V)1/3  , h = a/ sqrt(3)

Putting the values together, we get:

Surface Area = 3*a*a*sqrt(3) / 2;

Using this, the minimum surface area can be calculated.

### Spoj PRISMSA solution code:

```#include<bits/stdc++.h>
using namespace std;

int main()
{
std::ios::sync_with_stdio(false);
int t;
double vol,surface_area,a;
cin>>t;
while(t--)
{
cin>>vol;

/*the value of a calculated for minimum
Surface Area*/
a = pow(4*vol,0.3333333333333333333333333);
surface_area = 3*a*a*sqrt(3)/2;

cout << std::fixed << std::setprecision(10) << surface_area<<"\n";
}
return 0;
}```

# Spoj TETRA solution. Spoj Sphere in a tetrahedron  solution.

This question is based on geometry as we need to find the radius of the sphere subscribed inside an irregular tetrahedron

Required Radius = (3*volume of Tetrahedron)/(sum of surface areas of triangular faces).

This requires calculation of volume of Irregular Tetrahedron using its edge lengths.
This question can be seen as the extension of Spoj Pyramids Problem, in which volume of tetrahedron is calculated.

### Spoj TETRA solution code:

```#include <bits/stdc++.h>
using namespace std;

/*Heron's Formula to find area of a triangluar face*/
double areaHeron(double a1,double a2,double a3)
{
double s=(a1+a2+a3)/2.0;
return sqrt(s*(s-a1)*(s-a2)*(s-a3));
}

int main() {
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
double u,v,w,U,V,W,vol,a,b=12,total_area=0;
cin>>u>>v>>w>>W>>V>>U;

/*Adding total area of all sides*/
total_area += areaHeron(u,V,w);
total_area += areaHeron(W,u,v);
total_area += areaHeron(W,V,U);
total_area += areaHeron(U,v,w);

/*steps to calculate volume of a
Tetrahedron using formula*/
a=4*(pow(u,2)*pow(v,2)*pow(w,2))
- pow(u,2)*pow((pow(v,2)+pow(w,2)-pow(U,2)),2)
- pow(v,2)*pow((pow(w,2)+pow(u,2)-pow(V,2)),2)
- pow(w,2)*pow((pow(u,2)+pow(v,2)-pow(W,2)),2)
+ (
pow(v,2)+pow(w,2)-pow(U,2))*
(pow(w,2)+pow(u,2)-pow(V,2))*
(pow(u,2)+pow(v,2)-pow(W,2)
);
vol = sqrt(a);
vol /= b;

/*the radius of the inscribed circle
is (3*volume)/total_area */
cout << std::fixed << std::setprecision(4) << vol*3/total_area<<"\n";
}
return 0;
}```

# Spoj PIR solution. Spoj Pyramids solution.

This question is based on geometry as we need to find the volume of Irregular Tetrahedron using its edge lengths.
Here is the formula required:

### Spoj Pyramids solution code:

```#include <bits/stdc++.h>
using namespace std;

int main() {
std::ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
double u,v,w,U,V,W,vol,a,b=12;
cin>>u>>v>>w>>W>>V>>U;

/*steps to calculate volume of a
Tetrahedron using formula*/
a=4*(pow(u,2)*pow(v,2)*pow(w,2))
- pow(u,2)*pow((pow(v,2)+pow(w,2)-pow(U,2)),2)
- pow(v,2)*pow((pow(w,2)+pow(u,2)-pow(V,2)),2)
- pow(w,2)*pow((pow(u,2)+pow(v,2)-pow(W,2)),2)
+ (
pow(v,2)+pow(w,2)-pow(U,2))*
(pow(w,2)+pow(u,2)-pow(V,2))*
(pow(u,2)+pow(v,2)-pow(W,2)
);
vol = sqrt(a);
vol /= b;

cout << std::fixed << std::setprecision(4) << vol<<"\n";
}
return 0;
}```

This post deals with the question how to reverse a linked list? A linked list can be reversed either recursively or iteratively.

### Iterative Solution:

Here we use 3 pointers,
current, previous and next.

1. Change next pointer of current to point to previous.
2. Make prev = curr, curr = next.
3. Repeat the above process till we current is not NULL.

### Reverse a Linked List Problem Solution code in C++:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
struct node
{
int data;
node * next;
};

/*This function is used to add
new nodes to the Linked List*/
{
node *temp=new node;
temp->data=data;
}

/*This function is used to
{
{
}
cout<<endl;
}

/*This function is used to
{
node *prev=NULL;
node *next=NULL;
while(curr)
{
next=curr->next;
curr->next=prev;
prev=curr;
curr=next;
}
}

/*driver program to test the
above function*/
int main() {

cout<<"The reverse List is: \n";
return 0;
}```

Output:

```Original Linked List:
85 15 4 20
The reverse List is:
20 4 15 85```

Time Complexity: O(N) where N is the number of nodes in the linked list.

### Algorithm to reverse a linked list recursively:

1. Start from the head node, pointed to by “first”.
2. If the next node is null, return.
3. Traverse the list recursively.
4. Set first->next->next to first.
5. Set first->next to NULL.

### Solution code for reversing a Linked List recursively:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in
struct node
{
int data;
node * next;
};

/*This function is used to add
new nodes to the Linked List*/
{
node *temp = new node;
temp->data = data;
}

/*This function is used to
{
{
}
}

/*Function to reverse list*/
{

/*rest points to next of first*/
node* rest = first ->next;

/*if rest is the last node*/
if (rest == NULL)
{ return; }

/*recursive function call*/
reverse(&rest);

to second last node(new next)*/
first->next->next = first;

/*removes original links of the list*/
first->next = NULL;

}

/*driver program to test the
above function*/
int main()
{
cout<<" Entered list is: \n";

/*calling reverse function*/
cout<<"\nThe reverse List is: \n";
return 0;
}```

Output:

```Entered list is:
1 2 3 4 5
The reverse List is:
5 4 3 2 1
```

Time Complexity of reversing a linked list recursively is: O(N)
Space Complexity
of reversing a linked list recursively is: O(1)

# Print inorder traversal of a Binary Search Tree (BST) represented using array

Given a BST represented by an array, print inorder traversal of this array, i.e. print the elements of the array is such a way, that it represents the inorder Traversal of a BST.

### Print inorder traversal of a Binary Search Tree (BST) represented using array Example:

```Input:
4
/     \
2       6
/  \     /  \
1    3    5   7
This BST is stored in array as
arr[] = {4, 2, 6, 1, 3, 5, 7}

The Output should be:
1 2 3 4 5 6 7```

### Print inorder traversal of a Binary Search Tree (BST) represented using array Solution:

When a tree is stored using an array, then if the parent is given by the index i,
Then its
left child is given by index 2*i +1,
right child is given by index 2*i +2.

So, we recursively use first print the left subtree, followed by the present node and then the rescursively the right subtree.
We use the start and end indexes of the array to stop the recursion.

### Print inorder traversal of a Binary Search Tree (BST) represented using array code in C++:

```#include<bits/stdc++.h>
using namespace std;

void printInorder(int a[],int start,int end)
{
if(start>end)
return;
/*Printing the left subtree*/
printInorder(a,start*2+1,end);

/*printing present value*/
cout<<a[start]<<" ";

/*Printing the right subtree*/
printInorder(a,start*2+2,end);
}

int main()
{
int arr[] = {4, 2, 6, 1, 3, 5, 7};
int arr_size = sizeof(arr)/sizeof(int);
cout<<"The InOrder Traversal is:\n";
printInorder(arr, 0, arr_size-1);
return 0;
}```

Output:

```The InOrder Traversal is:
1 2 3 4 5 6 7```

Time Complexity: O(N) as all nodes are visited once.

# Remove Binary Search Tree (BST) keys outside a given range

Or Remove BST keys that don’t lie in given range/remove bina.

### Remove BST keys outside a given range Problem Statement:

Given a Binary Search Tree(BST) and a range say [ k1 , k2 ], remove all the nodes, whose values lie outside the given range.
While removing the nodes, the BST property is maintained.

### Remove BST keys outside a given range Example:

```Input:
10
/      \
5        20
/   \      /  \
1     7    15   25

Range = [6,22]
Output after Modification:

10
/    \
7      20
/
15```

### Remove Binary Search Tree (BST) keys outside a given range solution:

Here we follow POST-ORDER fashion to remove nodes.
This way when we reach a root node, its children are already processed and we do not need to worry about the sub-trees below this node.

When we find a node that is not in range, there can be two cases that arise:

1. Node’s data is smaller than the min value.
Here remove the root, and return the right subtree as the new root.
2. Node’s data is greater that the max value.
Here remove the root, and return the left subtree as the new root.

Note that when we return the left/right subtrees, they have already been processed.

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This funciton is used to Insert
new values in BST*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
if(!root)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}

/*This function deletes the nodes whose value
doesn't lie in range. It follows Postorder fashion*/
node *RemoveKeysNotInRange(node *root,int min,int max)
{
if(!root)
return NULL;

/*PostOrder fashion is followed*/
root->right=RemoveKeysNotInRange(root->right,min,max);
root->left=RemoveKeysNotInRange(root->left,min,max);

/*These Ifs are self explainatory*/
if(root->data < min)
{
node *temp=root->right;
delete root;
return temp;
}
if(root->data > max)
{
node *temp=root->left;
delete root;
return temp;
}
return root;
}

int main() {
/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

cout << "Inorder traversal of the given BST is: ";
Inorder(root);

root = RemoveKeysNotInRange(root, 6, 22);

cout << "\nInorder traversal of the modified BST is: ";
Inorder(root);
return 0;
}```

Output:

```Inorder traversal of the given BST is: 1 5 7 10 15 20 25
Inorder traversal of the modified BST is: 7 10 15 20```

Time Complexity: O(N) as all  nodes are visited once.

# Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST)

### Inorder Successor and Predecessor of a given Key in BST Problem Statement:

Given a Binary Search Tree (BST) and a key, you need to tell the values will precede and succeed the given key in the Inorder Traversal.
If the given key doesn’t exist in the BST, then print the values between which the given key will lie.

### Algorithm to find the Inorder Successor and Predecessor of a given Key in Binary Search Tree (BST):

1. Return if root is NULL.
2. If the root->data = key, then
1. If the Left subtree exists,
then the predecessor is the Rightmost node is the left subtree.
2. If the Right subtree exists,
then the Successor is the Left node is the Right subtree.
3. Return.
3. If root->data > key
1. set successor = root.
2. Recur on left Subtree.
4. If root->data < key
1. set Predecessor = root.
2. Recur on Right Subtree.

The above algorithm also works even if the key does’t exist in the tree. In that case, it gives the range in which the number lies.

### C++ code to find Inorder Successor and Predecessor of a given Key in BST :

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*This functio is used to create and
initialise new nodes*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This funciton is used to Insert
new values in BST*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*This function is used to find Inorder successor and
Predecessor. NOTE that we pass the variables by
reference */
void inorderPreSuc(node *root, node *&pre, node *&suc,int key)
{
if(!root)
return;
/*Here the key is found*/
if(root->data==key)
{
if(root->left)
{
/*Finding the Right most
node of left subtree*/

node *temp=root->left;
while(temp->right)
temp=temp->right;
pre=temp;
}
if(root->right)
{
/*Finding the left most
node of right subtree*/

node *temp=root->right;
while(temp->left)
temp=temp->left;
suc=temp;
}
return;
}
if(root->data > key)
{
suc=root;
/*Recur on left subtree*/
inorderPreSuc(root->left,pre,suc,key);
}
else
{
pre=root;
/*Recur on right subtree*/
inorderPreSuc(root->right,pre,suc,key);
}

}

int main() {
int key = 20;    //Key to be searched in BST

/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

node *pre = NULL, *suc = NULL;

inorderPreSuc(root, pre, suc, key);
/*Checking the existence of predecessor and
successor*/
if (pre)
cout << "Predecessor is " << pre->data << endl;
else
cout << "No Predecessor";

if (suc)
cout << "Successor is " << suc->data;
else
cout << "No Successor";

return 0;
}```

Output:

```Predecessor is 15
Successor is 25```

Time Complexity: O(H) where H is the height of the BST

# Convert BST to Greater Sum Tree

This problem can also be stated as BST to Binary Tree Conversion with data of nodes as the sum of all greater elements.

This program/question can be seen as an extension/ modification of converting BST to Binary Tree with data of nodes as sum of all greater value nodes.

### Convert BST to Greater Sum Tree Problem Statement:

Given a Binary Search Tree (BST), we need to add to each node, the sum of all greater values node.

### Convert BST to Greater Sum Tree Example:

```Input:
10
/      \
5        20
/   \      /  \
1     7    15   25

Output after Modification:

60
/      \
77        25
/   \      /  \
82    70    45   0```

NOTE: This program will convert a BST into a Binary Tree with value of nodes as the sum of all greater elements.

### Convert Binary Search Tree to Greater Sum Tree solution:

We use Reverse Inorder Traversal (recursion is called on right subtree first rather than left subtree) and maintain a variable to store the sum of nodes that have been traversed so far.

We then use this sum to modify the value of our present node, by first adding its value to the sum, and then replacing the value of the node with this sum.

#### C/C++ code for converting BST to Greater Sum Tree:

```#include <bits/stdc++.h>
using namespace std;

/*Stucture of each node of the tree*/
struct node
{
int data;
node *left;
node *right;
};

/*Function that allocates memory for
each new node and initialises it*/
node *newNode(int key)
{
node *temp=new node;
temp->left=NULL;
temp->right=NULL;
temp->data=key;
return temp;
}

/*This functions is used to print the
inOrder traversal of the array*/
void Inorder(node *root)
{
if(!root)
return;
Inorder(root->left);
cout<<root->data<<" ";
Inorder(root->right);
}

/*This function inserts new nodes
into the Binary Search Tree*/
node *Insert(node *root,int key)
{
if(!root)
return newNode(key);
if(key<root->data)
root->left=Insert(root->left,key);
else
root->right=Insert(root->right,key);
return root;
}

/*The function that uses reverse
value of all greater elements*/
{
if(!root)
return;

then replace the value in
node*/
sum += root->data;
root->data = sum - root->data;

}

/*utility function that hides
the actual implementation using
the above function*/
{
int sum=0;
}

int main() {
/* Let us create following BST
10
/    \
5     20
/  \    /  \
1    7  15   25 */
node *root = NULL;
root = Insert(root, 10);
Insert(root, 20);
Insert(root, 25);
Insert(root, 15);
Insert(root, 5);
Insert(root, 7);
Insert(root, 1);

cout<<"Initial BST Inorder Travesal:\n";
Inorder(root);
cout<<endl;

/*print inoder tarversal of
the modified BST*/
cout<<"Modified BST Inorder Travesal:\n";
Inorder(root);
cout<<endl;
return 0;
}```

Output:

```Initial BST Inorder Travesal:
1 5 7 10 15 20 25
Modified BST Inorder Travesal:
82 77 70 60 45 25 0```

Time Complexity: O(n) where n is number of nodes in the given BST.

# Lowest Common Ancestor (LCA) in Binary Search Tree (BST)

### Problem Statement LCA in a binary Search Tree (BST):

Given a binary search Tree(BST) and two numbers, we need to print the LCA of these two numbers numbers.
It can be assumed for simplicity that both these numbers exist in the given BST.

### LCA of two numbers:

Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).

### Lowest Common Ancestor in a binary Search Tree (BST) Example:

```        80
/  \
60   110
/  \   /  \
35  40  85 130```

Case I:
If the two numbers are 85 and 40 then the output is 80, as it is the only node that has both of these numbers as descendants.

Case II:
If the two numbers are 110 and 130 then the output is 110, as per the definition of LCA given above.

### Lowest Common Ancestor in a Binary Search Tree (BST) Solution:

Here we use recursion to find  the LCA of two number, there can be 3 cases that arise:

1. If both the numbers are less than the root’s data, then LCA lies in the left subtree,and we recur on it.
n1,n2<root’s data.
2. If both the numbers are greater than the root’s data, then LCA lies in the right subtree,and we recur on it.
n1,n2 > root’s data.
3. If any of the above case doesnt match, then we have our LCA as this node, print the data of this node.This case is combination of these 2 sub-cases:
1. If the root’s data lies between the two numbers.
n1<root’s data<n2 or n2<root’s data<n1.
2. If one of the number matches with the root’s data.
root’s data == n1 or n2.

#### Lowest Common Ancestor (LCA) in a Binary Search Tree (BST) Solution in c++:

```#include <bits/stdc++.h>
using namespace std;

/*Structure of each node of tree*/
struct node{
int data;
node *left;
node *right;
};

/*This function creates and
initialises new nodes*/
node * newNode(int data)
{
node * temp = new node;
temp->data=data;
temp->right=temp->left=NULL;
return temp;
}

/*This function inserts new nodes
int the Binary Search Tree*/
node * Insert(node * root, int data)
{
if(!root)
return newNode(data);

if(data<root->data)
root->left=Insert(root->left,data);
else
root->right=Insert(root->right,data);

return root;
}

/*This function is used or print the
LCA of two numbers*/
void LCA(node *root,int n1,int n2)
{
if(!root)
return;

/*If both numbers are smaller than
the root's data, then LCA lies on
left subtree*/
if(root->data >n1 && root->data >n2 )
return LCA(root->left,n1,n2);

/*If both numbers are greater than
the root's data, then LCA lies on
right subtree */
else if(root->data <n1 && root->data <n2 )
return LCA(root->right,n1,n2);
else
{
/*this case occurs when either of
the number matches with the root's
data or root's data lies in between
of the two numbers*/
cout<<"The LCA of "<<n1<<" and "
<<n2<<" is \n"<<root->data<<"\n";
return;
}
}

/* Driver Program to test above functions */
int main()
{
/* The following insertions create this
Binary Search Tree
80
/     \
60      110
/  \    /  \
35   40  85   130 */

node *root = NULL;
root = Insert(root, 80);
Insert(root, 110);
Insert(root, 85);
Insert(root, 130);
Insert(root, 60);
Insert(root, 40);
Insert(root, 35);

/*Finding LCA of n1 and n2*/
int n1=110,n2=130;
LCA(root,n1,n2);
LCA(root,85,40);
return 0;
}```

Output:

```The LCA of 110 and 130 is
110
The LCA of 85 and 40 is
80```

Time Complexity: O(H) where H is the height of the tree