This is my simple solution.

```
int countNodes(struct TreeNode* root) {
int height = -1, count, level, num_leaves;
struct TreeNode *node, *parent;
node = root;
for (node = root; node != NULL; node = node->left)
height++;
if (height == -1) {
return 0;
} else if (height == 0) {
return 1;
} else if (height == 1) {
if (root->right)
return 3;
return 2;
}
num_leaves = 1 << height;
for (level = 0; level < height; level++) {
count = 1;
for (parent = root, node = root->left; node->right != NULL;
parent = node, node = node->right) {
count++;
}
if (count == height - level) {
if (root->right == NULL) {
num_leaves--;
break;
} else if (root->right->left == NULL) {
if (node != root->left)
num_leaves -= ((1 << (height - level)) / 2);
break;
}
root = root->right;
} else {
num_leaves -= ((1 << (height - level)) / 2);
if (node->left != NULL) {
num_leaves--;
break;
} else if (node == root->left) {
num_leaves -= 2;
break;
} else if (parent->left->right != NULL) {
num_leaves -= 2;
break;
}
root = root->left;
}
}
return ((1 << height) - 1) + num_leaves;
}
```