The key idea is to find the mid node of current tree x: which is

x.right.left.left...left until null. Then use this mid to guide which subtree of x to go.

Search until reach the bottom leaf.

And during the searching process, we need to track the position of current tree's root in its level.

```
private int binarySearch(TreeNode root) {
/*
while the current tree is not leaf:
int comp = mid is null ?
if true: root = root.left, p = p*2
else: root = root.right, p = p*2 + 1. p: position
*/
// first get the Height of the tree.
int H = 0;
TreeNode x = root;
while (null != x) {
++H;
x = x.left;
}
// search for the last node in bottom level.
int p = 0;
int level = 0;
x = root;
while (null != x && !(x.left == null && x.right == null)) {
// mid.
TreeNode mid = x.right;
int searchDepth = level + 1;
while (null != mid) {
mid = mid.left;
++searchDepth;
}
if (searchDepth < H) { // mid: null: go left tree.
x = x.left;
p <<= 1; // p = 2*p + 0;
++level;
}
else {
x = x.right;
p = (p << 1) + 1; // p = 2*p + 1;
++level;
}
}
// nodes: the complete internal tree: 1 << (H - 1) - 1.
// nodes: bottom level: 1 + p
return p + (1<<(H - 1));
}
```