# Easy short c++ recursive solution

• ``````class Solution {

public:

int countNodes(TreeNode* root) {

if(!root) return 0;

int hl=0, hr=0;

TreeNode *l=root, *r=root;

while(l) {hl++;l=l->left;}

while(r) {hr++;r=r->right;}

if(hl==hr) return pow(2,hl)-1;

return 1+countNodes(root->left)+countNodes(root->right);

}

};``````

• nice solution. is there anyone who can tell how to calculate the time complexity of this one?

• There are at most lgn divisions, and lgn to calculate height within each division. So lgn * lgn

• Let n be the total number of the tree. It is likely that you will get a child tree as a perfect binary tree and a non-perfect binary tree (T(n/2)) at each level.

``````T(n) = T(n/2) + c1 lgn
= T(n/4) + c1 lgn + c2 (lgn - 1)
= ...
= T(1) + c [lgn + (lgn-1) + (lgn-2) + ... + 1]
= O(lgn*lgn)   ``````

• Using a extra function,the height of left branch could be calculate only once.below is my c solution

``````int recursiveCountWithHeight(struct TreeNode* root,int height) {
if(NULL==root) return 0;

struct TreeNode *p=root;
int r_h=0;
while(NULL!=p){
++r_h;
p=p->right;
}

if(height==r_h){
return pow(2,height)-1;
}else{
return 1+recursiveCountWithHeight(root->left,height-1)
+recursiveCountWithHeight(root->right,height-1);
}
}

int countNodes(struct TreeNode* root) {
if(NULL==root) return 0;

struct TreeNode *p=root;
int height=0;
// left height only needs to be calculated once
while(NULL!=p){
++height;
p=p->left;
}

return recursiveCountWithHeight(root,height);
}``````

• How "likely" is it?

• Does this solution work? You will need to re-calculate the left-height of right sub-tree right?

Perhaps should be

return 1+recursiveCountWithHeight(root->left, height-1) + countNodes(root->right);

• it is accepted.but on second thoughts I think u r right about it.when the right sub-tree is a complete tree and its height is one short than the left one,my solution will cause the calculation of the right part recursive needlessly,though it gives out the right answer,but the efficiency is reduced with no good reason.after modified the runtime of OJ is decrease from 74ms to 64 ms. thanks for your advice!

• ``````An improved method
pair<int,int> CountCompleteNodes(TreeNode* root)
{
if(!root)
{
return make_pair(0,0);
}
int LeftLevel = 1;
auto pLeft = root->left;
while(pLeft)
{
LeftLevel++;
pLeft = pLeft->left;
}
int RightLevel = 1;
auto pRight = root->right;
while(pRight)
{
RightLevel++;
pRight = pRight->right;
}
if(LeftLevel == RightLevel)
{
return make_pair(pow(2, LeftLevel)-1, LeftLevel);
}
auto RightNode = CountCompleteNodes(root->right);
if(LeftLevel == RightNode.second)
{
return make_pair(pow(2, LeftLevel-1)-1+RightNode.first, LeftLevel);
}else
{
auto LeftNode = CountCompleteNodes(root->left);
return make_pair(1+LeftNode.first+RightNode.first, LeftLevel);
}
}``````

• How is that an improvement? And where is the `countNodes` function?

• you either get two perfect binary tree or a perfect + a non-perfect. So a perfect + a non-perfect is already the worst case

as for how likely? (I could be wrong), there are possible (0 ~ 2^h) nodes in the bottom level. The only two cases that gives a perfect binary tree is 0, 2^h. So probability is (2^h + 1 - 2) / (2^h + 1)

• `1+countNodes(root->left)+countNodes(root->right);` Nice solution, Thank you!

• if pow(2,hl) is changed to be (1<<hl), the run time would decline from 360ms to 170 ms approximately.

• 1 + 2 + .. + h ~ O(h^2), where h = log(n)

• Wait. Should the recursion be:
T(n) = 2T(n/2) + c1 lgn ?
Am I correct? If so,
T(n) = 2^level * T(1) + c1 [lgn + lg(n-1) + ... + 1]
= n+ lgn
lgn = O(n)

• @Chauncey thanks for the improvement.

• @vanbasten23 no,in best case, left depth==right depth, so take constant time to calculate.
in the worst case, one of the left and right tree is a full tree, so T(n)=T(n/2)+....;

• I think as far likely is concerned, the probability is 1, because there is always a child tree which is complete at every level. There could be two child trees as full or just one.

• @redace85 I think this code is exactly the same but why does it TLE?

``````int countNodes(TreeNode* root) {
if(root == NULL) return 0;
TreeNode* l = root;
int hl = 0;
while(l){
l = l->left; hl++;
}
return countWithLeftHeight(root,hl);
}

int countWithLeftHeight(TreeNode* root, int hl){
if(root == NULL) return 0;
TreeNode* r = root;
int hr = 0;
while(r){
r = r->right; hr++;
}
if(hl == hr){
return (1<<hl) - 1;
}
return 1 + countWithLeftHeight(root->left,hl-1) + countWithLeftHeight(root->right,hl-1);
}``````

• nice solution~ i think height can be re-used when countNodes(root->left) like:

``````class Solution(object):
def left_height(self, root):
height = 0
while root is not None:
root = root.left
height += 1
return height

def right_height(self, root):
height = 0
while root is not None:
root = root.right
height += 1
return height

def count(self, root, left, right):
if left == -1:
left = self.left_height(root)
if right == -1:
right = self.right_height(root)
if left == right:
return 2**right-1
else:
return 1+self.count(root.left, left-1, -1)+self.count(root.right, -1, right-1)

def countNodes(self, root):
return self.count(root, -1, -1)

``````

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