|
|
back to boardwhy... this is wrong answer #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)); } |
|
|