So the idea is the following:

First check if we have a complete filled tree, if yes we know how much nodes we have: `2^h - 1`

where `h`

is the height of the tree.

Otherwise we know that the number of nodes = `2^(h-1) - 1 + lastLevel`

, where `lastLevel`

is the number of leafes on the last level.

To get the number of nodes on the last level, we do a D&C logic: first check if there is a *middle* node on the last level: Basically get the height of the most right node from the left of the current node. If the `mh`

height of that node equals to `h`

we have middle node otherwise not.

- if we have a middle node on the last level, we need to count on the right side + we know that on the left we had
`(1 << (h-2))`

. - if there is no middle, we know that we have less then
`(1 << (h-2))`

bottom nodes, and we continue our search on the left side.

```
public class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
// get the height of the most left node
TreeNode current = root;
int lh = 1;
while((current = current.left) != null) lh++;
// get the height of the most right node
current = root;
int rh = 1;
while((current = current.right) != null) rh++;
// if the left and right heights are the same, we have the last level filled,
// so: N = 2^h - 1
if(lh == rh) return (1 << lh) - 1;
// otherwise N = 2^(h-1) - 1 + <number of leaves>
return (1 << rh) - 1 + lastLevel(root, lh);
}
private int lastLevel(TreeNode root, int h) {
// if the height is 1, we have only 1 node
if(h == 1) {
return 1;
} else if(h == 2) {
// if the height is 2, we check left and right to count the last level nodes: 0, 1 or 2
return root.left == null ? 0 : (root.right != null ? 2 : 1);
}
// divide and conquer, first we find the 'middle' node on the last level
TreeNode mid = root.left;
int mh = 2;
while((mid = mid.right) != null) mh++;
if(mh == h) {
// we do have a middle node, so we know that the number of nodes on the last level=
// the number bottom nodes on the left side which is: (1 << (h-2))
// + the number of bottom nodes on the right side
return (1 << (h-2)) + lastLevel(root.right, h-1);
} else {
// if there is no middle node, we know that we must count them on the left side
return lastLevel(root.left, h-1);
}
}
}
```