# A Binary search mathod

• We use binary search on the last layer, the commentsin code shows details.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
bool leaf_is_null(TreeNode *r, int depth, int begin, int index)
{
// check whether the leaf is null
auto *ptr = r;
for(int i=depth-begin-1;i>=0;--i)
{
bool take_right = (index>>i) & 1;
if(take_right) ptr = ptr->right;
else ptr = ptr->left;
}
return ptr==nullptr;
}
public:
int countNodes(TreeNode* root) {
if(root==nullptr) return 0;
int r_level = 0, l_level = 0;
auto *ptr = root;

// first we get the depth of the tree
while(ptr!=nullptr)
{
++r_level;
ptr = ptr->right;
}
ptr = root;
while(ptr!=nullptr)
{
++l_level;
ptr = ptr->left;
}

if(l_level==r_level) return (1<<r_level) - 1;

// We know that the last node of the tree is in the d-th layer
// and is between the 0th and 2^(d-1)-1th node of the last layer,
// we can use binary search on the last layer.
// Using binary form of the index of nodes in the last layer,
// we can see that each 1 in the binary form now becomes
// an operation that we choose the right child,
// and each 0 represents the left child.
// Here we try to find the first null leaf in the last layer.
int l_bd = 0, r_bd = (1<<(l_level-1))-1, curr_level = 1;
ptr = root;
while(r_bd > l_bd)
{
int mid = max((l_bd + r_bd)>>1, 0);
if(leaf_is_null(ptr, l_level, curr_level, mid))
{
ptr = ptr->left;
r_bd = mid;
}
else
{
ptr = ptr->right;
l_bd = mid+1;
}
++curr_level;
}

return (1<<r_level) - 1 + l_bd;
}
};
``````

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