# From a naive traversal to two different simple clean recursive solutions and an optimized one in C

• ``````int leftHeight(struct TreeNode* root)
{
return !root? 0 : 1+leftHeight(root->left);
}

//AC - 152ms;
int countNodes(struct TreeNode* root)
{
if(!root) return 0;
int lHeight = leftHeight(root->left);
int rHeight = leftHeight(root->right);
return lHeight == rHeight? pow(2, lHeight)-1 : (1 << rHeight) + countNodes(root->left);
}

//AC - 144ms;
int countNodes(struct TreeNode* root)
{
if(!root) return 0;
int lHeight=0, rHeight=0;
for(struct TreeNode* l=root; l; l=l->left) lHeight++;
for(struct TreeNode* r=root; r; r=r->right) rHeight++;
if(lHeight==rHeight) return (1<<lHeight)-1;
return countNodes(root->left)+countNodes(root->right)+1;
}

//AC - 90ms
int countNodes(struct TreeNode* root)
{
if(!root) return 0;
int lHeight=0;
int rHeight=0;
for(struct TreeNode* t=root->left; t; t=t->left) lHeight++;
for(struct TreeNode* t=root->right; t; t=t->left) rHeight++;
if(lHeight==rHeight)
{
rHeight = 0;
for(struct TreeNode* t=root; t; t=t->right) rHeight++;
if(lHeight==rHeight-1) return (1<<rHeight)-1;
else return (1 << lHeight)+countNodes(root->right);
}
else return (1 << rHeight) + countNodes(root->left);
}``````

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