18ms beats 100% Java Solution with BST

• ``````class MedianFinder {
class TreeNode{
int val;
TreeNode parent,left,right;
TreeNode(int val, TreeNode p){
this.val=val;
this.parent=p;
left=null;
right=null;
}
if(num>=val){
if(right==null)
right=new TreeNode(num,this);
else
}else{
if(left==null)
left=new TreeNode(num,this);
else
}
}
TreeNode next(){
TreeNode ret;
if(right!=null){
ret=right;
while(ret.left!=null)
ret=ret.left;
}else{
ret=this;
while(ret.parent.right==ret)
ret=ret.parent;
ret=ret.parent;
}
return ret;
}
TreeNode prev(){
TreeNode ret;
if(left!=null){
ret=left;
while(ret.right!=null)
ret=ret.right;
}else{
ret=this;
while(ret.parent.left==ret)
ret=ret.parent;
ret=ret.parent;
}
return ret;
}
}
int n;
TreeNode root, curr;
// Adds a number into the data structure.
if(root==null){
root = new TreeNode(num,null);
curr=root;
n=1;
}else{
n++;
if(n%2==1){
if(curr.val<=num)
curr=curr.next();
}else
if(curr.val>num)
curr=curr.prev();
}
}

// Returns the median of current data stream
public double findMedian() {
if(n%2==0){
return ((double)curr.next().val+curr.val)/2;
}else
return curr.val;
}
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();