# binary search. java. 44ms. 99% beat

• 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));
}

``````

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