# 80 ms C++ non-recursive solution

• ``````class Solution {
public:
int countNodes(TreeNode* root) {
int res = 0;
int lh = 0, rh = 0;
while(root){
if(!lh){
for(TreeNode * p = root->left; p; p = p->left)
++lh;
}
if(!rh){
for(TreeNode * p = root->right; p; p = p->left)
++rh;
}
if(lh == rh){
res += 1<<lh;
root = root->right;
--lh;
rh = 0;
}else{
res += 1<<rh;
root = root->left;
--lh;
rh = 0;
}
}
return res;
}
};
``````

• @biwuxia
I have another non-recursive solution using binary search.
The key idea is to check if the k-th node exists by moving the 'node' pointer from 'root' to the right direction.

``````class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
int height = 0;
TreeNode* n = root;
while (n != NULL) {
++height;
n = n->left;
}

int hi = (1<<(height-1)), low = 0;

while (low < hi) {
int mid = low + (hi - low) / 2;

// Find the mid-th element of the bottom level.
n = root;
for (int h = height - 1; n != NULL && h > 0; --h) {
if (mid & (1 << (h-1))) {
n = n->right;
} else {
n = n->left;
}
}

if (n == NULL) {
hi = mid;
} else {
low = mid + 1;
}
}
return (1<<(height-1)) + hi - 1;
}
};
``````

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