# Simple BST solution

• ##BST solution

``````public class MedianFinder {
private Tree tree ;
/** initialize your data structure here. */
public MedianFinder() {
tree = new Tree();
}

}

public double findMedian() {
int size = tree.size();
int half = size >> 1;
if(size %2 == 1){
return tree.getIth(1 + half);
}
else{
return (tree.getIth(half) + tree.getIth(half +1)) / (double)2;
}
}
}

// BST
class Tree{
private static class Node {
int cnt;
int value;
Node left;
Node right;

Node(int v){value = v; cnt = 1;}
}

private Node root ;

if(root == null){
root = new Node(n);
return ;
}

// root not null.
Node cur = root;

while(true){
cur.cnt ++; // important
if(n < cur.value){
if(cur.left == null){
cur.left = new Node(n);
break;
}
cur = cur.left;

}
else{
if(cur.right == null){
cur.right = new Node(n);
break;
}
cur = cur.right;
}
}
}

// get ith largest element, i is 1-based.
int getIth(int i){
if(i <= 0 || i > size()) throw new RuntimeException("wrong args: " + i);

Node cur = root;
while(true){
int leftCnt = cur.left == null ? 0: cur.left.cnt;
int rightCnt = cur.right  == null ? 0: cur.right.cnt;

if(leftCnt + 1 == i) // root.
return cur.value;
else if(leftCnt >= i){
cur = cur.left;
}
else{
cur = cur.right;
i -= (1 + leftCnt);
}
}
}

int size(){
return root == null ? 0: root.cnt;
}
}``````

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