# 29ms c++ binary search solution

• first we have a parent node root, like binary search ,it has two choice.

• First if it's left child is a full binary tree, adding the count of left child's leaf.And then root = root->right, go to it's right child.

• Second if it's left child isn't a full binary tree, so root = root->left.

Because this tree is a complete tree, you can find a node , it is a full binary tree.
'''
int countNodes(TreeNode* root) {
int Deep = 0, result = 0;
if (!root) return 0;
TreeNode* temp = root, *child = root;//calculate the height of this tree
while(temp) {
Deep++;
temp=temp->left;
}
int parentHigh = Deep;//the height of current node

``````    while (parentHigh>1) {//parentHigh is range 2 to Deep, because
child = root->left;//this node's child
int childHigh = parentHigh-1;//the height of current node's child
for (int i = childHigh; i > 1; i--) child = child->right;//iterate child node from childHigh to 1
if (child) {//if childtree is a full tree, the child isn't null, so the right child may be not a full tree
root = root->right;//and then binary search parent's right subtree
result += 1<<(childHigh-1);//add the count of full binary tree's leaf
}else{//if not, after iterating child will be null.
root=root->left;
}
parentHigh--;//downward the parent
}
if (root) result++;//if root is full binary tree, you need add the last node
return result + (1<<(Deep-1))-1;
}
``````

''''

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