# Beating 99.84% submissions in C++, quite intuitive and well-commented

• What are we doing here is to collect the additional last-level `leaves`, always stick this in mind when reading the code below.

``````class Solution {
public:
int countNodes(TreeNode* root)
{
if(!root) return 0;
int height = 0, sum = 0, i = 0;
TreeNode *t = root, *t0 = NULL;
while(t) t = t->left, height++; //get the height of the tree;
t = root;
int level = height - 2; //levels under the child of root;
while(level > -1) //collect the bottom-level nodes by halving them apart;
{
t0 = t->left;
for(i = 0; i < level; ++i) t0 = t0->right;
if(t0) { sum += 1<<level; t = t->right; } //rightmost node is not null;
else t = t->left;
level--; //move to the next level;
}
if(t) sum++; //if it's a complete tree, collect the last right node;
return sum+((1<<(height-1))-1);
}
};``````

• Another binary-search solution is also enclosed here.

One reminder here: the time cost is accelerated from `248ms` to `124ms` just by replacing the `pow(2, r)` to `(1<<r)`.

``````class Solution {
private:
int lheight(TreeNode* root)
{
int depth = 0;
while(root) root = root->left, depth++;
return depth;
}
public:
int countNodes(TreeNode* root)
{
if(!root) return 0;
int l = lheight(root->left), r = lheight(root->right);
if(l > r) return countNodes(root->left)+(1<<r);
else return countNodes(root->right)+(1<<l);
}
};``````

• Then using in-line `loop` to replace function invoking, reduce the time to `112ms`.

``````class Solution {
public:
int countNodes(TreeNode* root)
{
if(!root) return 0;
int lCount = 0, rCount = 0;
for(TreeNode* l = root->left; l; l = l->left) lCount++;
for(TreeNode* r = root->right; r; r = r->left) rCount++;
if(lCount > rCount) return countNodes(root->left)+(1<<rCount);
else return countNodes(root->right)+(1<<lCount);
}
};``````

• Using iterative solution to update the previous recursive one reduce the time to `100ms` now.

``````class Solution {
public:
int countNodes(TreeNode* root)
{
if(!root) return 0;
int sum = 0, lCount = 0, rCount = 0;
while(root)
{
lCount = 0, rCount = 0;
for(TreeNode* l = root->left; l; l = l->left) lCount++;
for(TreeNode* r = root->right; r; r = r->left) rCount++;
if(lCount > rCount) root = root->left, sum += (1<<rCount);
else root = root->right, sum += (1<<lCount);
}
return sum;
}
};``````

• Conclusion:

Compared to the best submission `72ms`, all the solutions above have done lots of re-checking when measuring the height, while the best only check it once and then all the following checking will only take one traversal while the other solutions are doing two - left and right.

• @LHearen Smart!

• @LHearen
Your algorithm of first solution is brilliant and unusual. Usually a algorithm of Tree consider the the left and the right child, but you are considering the left child's left and right path.
Somehow this requires a hard-memorization to utilize your algorithm in interview.

One thing that bothers me is your comment on this line, which I think is misleading:
if(t) sum++; //if it's a complete tree, collect the last right node;
collect the last right node is an accurate description, but I don't see why you want to say it is a complete tree.
Apparently when you quit the loop while(level > -1) , t is at the bottom level, either a NULL pointer or left child of its parent and no right sibling.
I think the comment should be //if it's the single left child of it's parent, we add it to the sum (pow(2, 0) )

Regards,

Quesder

• @quesder Your observation is sharp indeed, however what I exactly meant here is the `t` instead of `t0` (the child of `t`) at the last loop, if the `t0` is again valid then `t` will move to its right child (the last only leaf), which is why I will check it and if it's a leaf not `NULL` then I added `a perfect complete tree` comment.

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