ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1306. Sequence Median

Posted by Iqramul Islam 6 Jan 2019 11:18
#include <iostream>
using namespace std;

/// A BST...
struct Node
{
double data;
struct Node *left, *right;
};
///function to create new Node in BST
struct Node *newNode(double item)
{
struct Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
///function to insert a new Node
/// with given key in BST
struct Node* insert(struct Node *node, double key)
{
///if tree is empty, return a new node
if(node==NULL)
return newNode(key);
///otherwise, recur down the tree..
if(key <node->data)
node->left = insert(node->left, key);
else if (key >node->data)
node->right = insert(node->right, key);

return node;
};

double counNodes(struct Node *root)
{
struct Node *current, *pre;

double count = 0;
if(root==NULL)
return count;

current=root;
while(current!=NULL)
{
if(current->left==NULL)
{
count++;
current=current->right;
}
else
{
pre = current->left;
while(pre->right !=NULL &&
pre->right !=current)
pre = pre->right;
if(pre->right==NULL)
{
pre->right=current;
current = current->left;
}
else
{
pre->right = NULL;

count++;
current = current->right;
}
}
}

return count;
}

///Function to find median in o(n) time and O(1) space...
double findMedian(struct Node *root)
{
if(root == NULL)
return 0;

int count = counNodes(root);
int currCount = 0;
struct Node *current = root, *pre, *prev;

while (current!= NULL)
{
if(current->left == NULL)
{
currCount++;
///odd case..
if(count %2 !=0 && currCount == (count+1)/2)
return prev->data;
///Even case...
else if(count%2==0 && currCount == (count/2)+1)
return (prev->data + current->data)/2;

///Update prev..for even no. of nodes...
prev = current;

current = current->right;
}
else
{
///Find inorder predecessor of current...
pre = current->left;
while(pre->right!= NULL && pre->right!=current)
pre = pre->right;
/// make current as right child of in. pre.dec.
if(pre->right == NULL)
{
pre->right = current;
current = current->left;
}
/// revert the changes.. made in if part
/// to restore the original tree.. , fix the right chid of predecessor...

else
{
pre->right = NULL;
prev = pre;

currCount++;

if(count%2!=0 && currCount == (count+1)/2)
return current->data;
else if (count%2!=0 && currCount == (count/2)+1)
return (prev->data+current->data)/2;
///Update...for even case...

prev = current;
current = current->right;
}
}
}
}

int main()
{
struct Node *root = NULL;
int n;
double x;
cin >> n;
cin >> x;
root = insert(root, x);
for(int i=1; i<n; i++)
{
cin >> x;
insert(root, x);
}
//cout << findMedian(root);
//if(n%2==0)
printf("%.1f", findMedian(root));

}