WAP Convert Set of Nodes of Binary Tree where each node contains two value i, j & i value follow BST property , j value follow Heap Property, Build BST form these Nodes.

A rooted binary tree with keys in its nodes has the binary search tree
property (BST property) if, for every node, the keys in its left
subtree are smaller than its own key, and the keys in its right
subtree are larger than its own key. It has the heap property if, for
every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an
integer i and an integer j. No two i values are equal and no two j
values are equal. We must assemble the nodes into a single binary tree
where the i values obey the BST property and the j values obey the
heap property. If you pay attention only to the second key in each
node, the tree looks like a heap, and if you pay attention only to the
first key in each node, it looks like a binary search tree.Describe a
recursive algorithm for assembling such a tree

Indirectly They Asked to Implement Treap

Data Structure: Treap( Heap + Binary Search Tree)

Algorithm:
1.Sort the nodes in decreasing order of their j values and then simply build the
2.BST according to the i values starting from the first node in the obtained sorted
list. The first node will be the root. For example, let the given nodes (i,j
pairs) be:

so our structure of node will looks like this

struct node
{
int i;
int j;
struct node *left;
struct node *right;
};



For Example:
(12,6) (18,25) (19,10) (17,5) (19,10) i.e. 5 nodes
nodes after sorting in decreasing order according to j values:
(18,25) (16,11) (19,10) (12,6) (17,5)
So the tree would be something like this:


(18,25)
|
| |
(16,11) (19,10)
|
| |
(12,6) (17,5)


Working Code:


#include
#include



struct node
{
int i;
int j;
struct node *left;
struct node *right;
};


void mySwap(struct node **n1, struct node **n2)
{
struct node *tmp;
tmp = *n1;
*n1 = *n2;
*n2 = tmp;
}


struct node *myInsert(struct node *root, struct node *nodeToInsert)
{
if(root == NULL)
{
return nodeToInsert;
}
else
{
if(nodeToInsert->i <= root->i)
{
root->left = myInsert(root->left,nodeToInsert);
}
else
{
root->right = myInsert(root->right,nodeToInsert);
}
return root;
}
}


void myFunc(struct node *arr[], struct node **resultTree, int size)
{
if(!size)
return;
int ind;
int maxInd = 0;
for(ind=0;indj > arr[maxInd]->j)
maxInd = ind;
*resultTree = myInsert(*resultTree,arr[maxInd]);//inserting node with maximum j value
mySwap(&arr[maxInd],&arr[size-1]);
myFunc(arr,resultTree,size-1);
}


int main()
{
int n;
struct node *arr[100];
scanf("%d",&n);
int ind;
int ival,jval;
struct node *result = NULL;
for(ind=0;indi = ival;
arr[ind]->j = jval;
arr[ind]->left = NULL;
arr[ind]->right = NULL;
}
myFunc(arr,&result,n);
//levelOrderTraversal(result);
//PreOrderTraversal(result);
for(ind=0;ind free(arr[ind]);
return 0;
}

Solution Given BY Vipul

Time Complexity O(N^2)
Space Complexity O(logn)
Run Here https://ideone.com/o7dfU