# Solution using Binary Search Tree

• As the input numbers are random, so the height of the binary search tree is O(logN)

We maintain every single node's children's size and it's easy to implement because it just has add operation.

``````struct BST {
struct node {
int val;
int size;
node* left, *right;
node(int v) : size(1), val(v) {};
} *Null, *root;

BST() {
Null = new node(0);
Null -> size = 0;
root = Null;
}

void add(int val, node*& R) {
if(R == Null) {
R = new node(val);
R -> left = R -> right = Null;
return;
}
R->size = R->left->size + R->right->size + 1;

}

int rank(int k) {
node* t = root;
while(true) {
int leftSize =  t -> left -> size;
if(leftSize == k) return t -> val;
if(leftSize > k) {
t = t -> left;
} else {
k = k - leftSize - 1;
t = t -> right;
}
}
return -1;
}
};

class MedianFinder {
public:
BST* bst;
MedianFinder() {
bst = new BST();
}
// Adds a number into the data structure.
}

// Returns the median of current data stream
double findMedian() {
int sz = bst -> root -> size;
if(sz % 2 == 0) {
return 1.0 * (bst -> rank(sz / 2) + bst -> rank(sz / 2 - 1)) / 2;
} else return bst->rank(sz / 2);

}
};``````

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.