GetMedian

class Node {
  Node left;
  Node right;
  int treeSize;
  int val;
}

public float getMedian(Node root) {
  if (root == null) {
    return 0; // not sure how you want to handle empty tree
  }
  final int N = root.treeSize;
  if (N % 2 == 0)
    return 0.5 * (findKth(root, N / 2) + findKth(root, N / 2 + 1));
  else
    return (float) findKth(root, N / 2 + 1);
}

public int findKth(Node n, int k) {
  final int leftSize = (n.left == null) ? 0: n.left.TreeSize;
  
  if (leftSize == k - 1) {
    return n.val;
  } else if (leftSize > k) {
    return findKth(n.left, k);
  } else {
    return findKth(n.right, k - 1 - leftSize);
  }
}