public int countNodes(TreeNode root) {

int num = 0;

//boundary condition

if(root == null) return 0;

if(root.left == null && root.right == null) return 1;

```
//get the depth of the tree
TreeNode tmp = root;
int depth = 0;
while(tmp != null){
depth ++;
tmp = tmp.left;
}
int curDepth = depth;
//binary search
while(root != null){
int leftDepth = curDepth - 1, rightDepth = 0;
TreeNode right = root.right;
//get the depth of the right child
while(right != null){
rightDepth ++;
right = right.left;
}
if(leftDepth > rightDepth){
num += 1 + Math.pow(2, leftDepth - 1) - 1;
root = root.left;
}
else{
num += 1 + Math.pow(2, leftDepth) - 1;
root = root.right;
}
curDepth = leftDepth;
}
return num;
}
```